本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-13 15:30:21

树形DP常用优化

主要是通过利用 DFN 序的一些巧妙性质及利用，从而实现优化常数甚至是优化复杂度。

1.树形背包

例如 P2014 [CTSC1997] 选课

我们在正常进行树形背包时，需要进行 $3$ 层循环，时间复杂度为 $O(n^3)$ 。

code

for(int i = 0;i < G[u].size();i++)
	{
		int v = G[u][i];
		for(int j = m;j >= 1;j--)
		{
			for(int k = 0;k < j;k++)
			{
				dp[u][j] = max(dp[u][j],dp[u][j-k] + dp[v][k]);
			}
		}
	}

但我们可以考虑将以 $u$ 为根的子树拍扁,这样我们就相当于是在子树内进行了一次 $0/1$ 背包，由于最终答案都是由子树合并来，而子树之间的数量关系也不会相互影响，所以我们直接将其拍扁，这样进行树形背包的复杂度是 $O(n^2)$ 的。

code

for(int i = 1;i <= n + 1;i++)
	{
		int u = d[i];
		for(int j = 0;j <= m;j++)
		{
			f[i][j] = f[i - size[u]][j];
			if(j) f[i][j] = max(f[i][j],f[i-1][j-1] + s[u]);
		}
	}

2.$DFN$ 优化递归常数

同样的，我们这种利用 $DFN$ 而避免使用递归合并 $dp$ 数组的方法可以极大的优化递归常数。

例如P3523 [POI 2011] DYN-Dynamite

我们在由子树向根合并 $dp$ 值的时候，通过 $DFN$ 避免了使用 $dfs$ 递归带来的大常数，在一些极端数据下可以使我们的代码跑的飞快。

详见分析

3.通过减少合并次数降低复杂度

常见的，我们可以通过树的链剖分以及树上 lca ，使得子树或一条链内的所有节点都合并到链头的位置，从而可以优化合并的复杂度。

未完待续。