1. 树上背包的复杂度疑问从哪里来

如果有人问我，算法竞赛里最像魔术的一个复杂度结论是什么，我会说是树上背包的合并操作：明明每个节点都要把儿子子树合并进来，每次合并又是一层接近 O(n^2) 的枚举，为什么算出来总复杂度不是 O(n^3)，而是 O(n^2)？

这个问题我当年第一次接触时也卡了很久。后来带学弟学妹训练，发现几乎每个人都会在这个Trick上纠结一遍。所以这篇文章就把这个"Trick 树上背包合并复杂度分析"完整拆开，从直觉误区、证明方式、代码实现到调试经验一次讲透。适合刚学树形DP、准备竞赛，或者想彻底搞懂树上背包复杂度的同学。

先明确我们讨论的问题长什么样。最常见的模板是"选课问题"：给定一棵树，每个节点有一个价值，选一个点之前必须选它的父亲，最多选 m 个点，问最大总价值。经典做法是用树形DP，dp[u][k]表示在 u 的子树里选 k 个点，并且 u 已经被选中时的最大价值。转移的时候，要把 u 的每个儿子 v 的子树当成一组待合并的物品，像普通背包那样滚进去。

这时候一眼看过去，每个节点都要枚举 i 和 j，两重循环，外面再套一层 DFS，复杂度怎么想都像 O(n^3)。很多初学者就在这里开始怀疑人生：这么简单的转移，难道真的有三重循环？其实三重循环确实有，但第三层循环不是凭空多出来的 n，合在一起反而被限制住了。关键就在于"合并"这两个字上。

要理解这个复杂度结论，不能站在"节点数 × 背包容量"的角度去乘，而要站在"合并次数"的角度去看。接下来我会先给一个直观证明，再给一份可以直接抄的代码，最后讲一些我自己踩过的坑。

2. 复杂度上界的直观证明：每个点对只相遇一次

2.1 把一次合并拆开看

先看标准转移代码里的一次合并。假设当前处理到 u，已经合并完了一部分儿子，这部分总大小为a；现在要把儿子 v 合并进来，v 的子树大小为b。合并时做的事，是枚举 i 从 1 到 a，j 从 1 到 b，然后尝试用dp[u][i] + dp[v][j]更新dp[u][i+j]。这一轮合并的枚举次数就是a * b。

这个a * b的几何意义很直接：它相当于把"u 已经处理过的那一堆节点"和"v 子树里的这一堆节点"做了一次笛卡尔积。你可以想象成两拨人见面，旧集合里每个节点都要和新集合里每个节点配对一次。注意，这里说的是"节点作为占位单元"的配对次数，而不是具体方案数。虽然 DP 数组里存的是压缩后的最大值，但循环确实是老老实实把a * b种组合都扫了一遍。

有了这个视角，复杂度问题就变成一个计数问题：整棵树的合并过程中，到底会发生多少次这样的"跨集合配对比试"？

2.2 为什么答案是 O(n^2)

关键性质是：任意两个节点 x 和 y，它们只会在一个特定的时机被纳入同一次"配对统计"里。

设 x 和 y 的最近公共祖先为 t。当 DFS 处理到 t、准备合并某个儿子分支时，如果 x 已经在前面处理过的儿子分支里，y 在当前这个儿子分支里，那么这次合并的枚举里就会有(x, y)这一对。等这次合并结束，x 和 y 就进入同一个"已处理集合"了，之后不管再合并什么子树，它们都是作为一个整体出现，不会再作为"一个在旧集合、一个在新集合"的配对被枚举第二次。

而任意两个不同的节点，它们的最近公共祖先是唯一的。所以在整棵树的合并过程中，每个点对最多被计数一次。n 个节点一共有n * (n - 1) / 2个点对，因此所有合并操作的总枚举次数就是 O(n^2)。

这个解释我第一次听到时觉得太漂亮了，它完全绕开了复杂的递推式，直接用"LCA唯一性"把上界钉死。后来我也见过不少严谨的证明写法，本质都是这个双重计数：每次合并的a * b次枚举，总能映射到一组"来自两个不同已处理集合的节点对"，而每个节点对只会被映射一次。

2.3 正规推导：递归式也能推出同样结论

如果你需要用递推式写题解，可以这样写：设T(u)表示处理 u 子树内所有合并操作的总代价，那么有

T(u) = sum(T(v)) + 合并开销

其中合并开销是sum(已并入大小 * 当前子树大小)。把这一项按"每个点对只贡献一次"来重新分配，就能得到T(root) = O(n^2)。数学上这等价于证明了：

sum over u (sum over v child of u (sz_before * sz_v)) <= n * (n - 1) / 2

这里的sz_before是合并 v 之前已经并入的所有儿子子树大小之和。这个式子在做复杂度分析时非常常用，建议直接记下来。

3. 从 O(n^3) 到 O(n^2) 的代码实现细节

3.1 标准写法：循环上限必须用 sz 裁剪

下面是一份最常见的树上背包核心代码，选课问题，每个点体积为 1：

#include <bits/stdc++.h> using namespace std; const int N = 2005; const int INF = 1e9; int n, m; int val[N]; int dp[N][N]; int sz[N]; vector<int> g[N]; void dfs(int u, int fa) { // 只选自己：状态为 1 dp[u][1] = val[u]; sz[u] = 1; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); // 合并 v 的子树进 u for (int i = min(m, sz[u]); i >= 1; --i) { for (int j = 1; j <= min(m - i, sz[v]); ++j) { dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j]); } } // 合并完才把 v 的大小加进来 sz[u] += sz[v]; } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { int pre, val_i; scanf("%d%d", &pre, &val_i); val[i] = val_i; if (pre != 0) { g[i].push_back(pre); g[pre].push_back(i); } } dfs(1, 0); printf("%d\n", dp[1][m]); return 0; }

这份代码有三个细节值得反复看。

第一个细节是sz[u]在循环前不能包含 v。因为dp[u][i]的含义是"已经合并完的那部分儿子"里的状态，如果把当前 v 的子树也算进sz[u]，枚举范围就会变大，复杂度理论上会被破坏，实际也会算出重复选 v 的错误答案。所以正确的顺序一定是：先枚举合并，再执行sz[u] += sz[v]。

第二个细节是 i 必须倒序。原因和普通 01 背包一样：dp[u][i]应该被当作旧值使用。如果正序枚举，dp[u][i+j]更新完之后，后面的循环又可能拿这个新值去更新更大的容量，相当于把同一棵子树的物品用了多次。初学者最常见的错误就是这里写成正序，最后答案偏大，又查不出原因。

第三个细节是 j 也只能枚举到min(m - i, sz[v])。很多人知道 i 要裁剪，却忘了 j 也可以裁剪。如果 j 枚举到m - i甚至m，当sz[v]远小于容量上限时，会有大量无效状态参与运算，虽然答案不至于错，但复杂度会退化。比如 m 很大、树是一条链时，每个节点都枚举m * m次，那真的会回到 O(n^3)。

3.2 更稳的写法：先复制一份 old 数组

如果你觉得倒序循环容易记混，或者题目状态比较复杂，我推荐一种更稳的写法：每次合并前，把dp[u]的前sz[u] + 1项复制到一个临时数组old，然后用old[i] + dp[v][j]去更新dp[u][i+j]。这样不管 i 正序还是倒序，都不会出现"用本轮新值更新其他状态"的问题。

int old[N]; // 临时数组，注意放在 dfs 外部避免反复分配 void dfs(int u, int fa) { dp[u][1] = val[u]; sz[u] = 1; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); // 只复制有效部分，不要整个数组都拷贝 for (int k = 0; k <= min(m, sz[u]); ++k) old[k] = dp[u][k]; for (int i = min(m, sz[u]); i >= 1; --i) { for (int j = 1; j <= min(m - i, sz[v]); ++j) { dp[u][i + j] = max(dp[u][i + j], old[i] + dp[v][j]); } } sz[u] += sz[v]; } }

很多人会担心这样拷贝会不会让复杂度变高。其实不会，因为每次拷贝的长度就是当前sz[u]的大小，和合并枚举量是同一个量级，整个过程中拷贝的总代价依然是 O(n^2)。我实际用下来，这个写法的好处是：即使 i 循环顺序写错，答案也不容易错，排查问题的时间大幅减少。代价只是多了一个 old 数组的拷贝开销，常数略大，但绝大多数题目完全能接受。

3.3 容量截断后的复杂度会变成 O(n*m)

上面讨论的是 m 和 n 同阶、枚举范围由 sz 主导的情况，结论是 O(n^2)。但如果 m 很小，循环范围会被min(m, ...)截断，这时候复杂度就不再是严格 O(n^2)，而是 O(n*m)。

原因也可以从点对计数角度理解：每个点对虽然理论上只被计数一次，但当容量上限 m 小于子树大小时，大量点对会因为枚举范围被裁剪而不再产生枚举单元。最终的枚举总量不会超过O(n*m)。这个结论在很多题解里会被直接拿来用，比如 n 是 2e5、m 是 100 时，树上背包用这个Trick就是标准解法。

不过要注意，这个O(n*m)是容量限制严格生效时的复杂度。如果你把循环上限写成i <= m、j <= m - i而不是i <= min(m, sz[u])、j <= min(m - i, sz[v])，那仍然可能退化成近似 O(n*m^2)。所以即使 m 很小，"用 sz 裁剪"的习惯也不能丢。

3.4 初始化是个隐蔽的坑

树上背包的初始化看起来简单，但真的会写错。常见的有两种设定：

第一种是"选了 u 才能选子树里的点"，那么dp[u][1] = val[u]，dp[u][0] = 0表示子树里一个都不选。注意dp[u][0]必须是合法状态，因为合并儿子时 i 从 1 开始不会用到它，但最终答案可能需要不选整棵子树。

第二种是"u 可选可不选"，那么你需要另外维护一个状态表示"不选 u 也能选子树"的情况。有些题目会把这个问题简化成加一个虚拟根，给虚拟根设价值 0，再跑标准写法，这样就不需要额外分类讨论了。我建议初学者直接记"加虚拟根"这个套路，比手动维护两个状态数组不容易错。

另外，如果价值会出现负数，dp数组必须初始化为一个足够小的负值，而不是 0。很多人题目看漏了"价值可能为负数"这个条件，直接把数组清成 0，结果答案全是 0。我自己的习惯是统一初始化成-INF，只把合法状态单独赋值，这样无论价值正负都不会出问题。

4. 应用场景与复杂度陷阱

4.1 哪些题目能用这个Trick，哪些不能

"每个点体积为 1"是上面复杂度分析的核心前提。一旦每个点的体积不是 1，比如第 i 个点需要消耗w[i]的体积，合并复杂度就不能简单地用sz来刻画了。因为两个子树合并时，枚举的是一系列体积组合，而不是按节点个数枚举，a * b这个"点对计数"就不成立了。这时候最坏复杂度可能退化到 O(n * V^2)，V 是体积上限。

还有一种情况是 DP 状态带了额外维度，比如"选了多少个点 + 总价值不超过某值"或者"同时限制体积和价值"。只要合并时多出一层关键枚举，复杂度结论就需要重新推导，不能直接套 O(n^2)。

反过来，以下场景仍然适用这个Trick：

• 树上选恰好 k 个点，且每个点体积为 1（选课、依赖背包的常见变体）。
• 每个节点可选多次或不选（完全背包版），只要合并时枚举的还是子树大小和容量。
• 需要输出方案、需要统计方案数，只要转移本质不变，复杂度结论也不变。

4.2 长链剖分和树上背包的区别

很多人会把树上背包的 O(n^2) 和长链剖分的 O(n) 优化搞混。长链剖分解决的是另一类"深度相关"的树形DP，它通过共用数组来避免重复分配，把时间做到 O(n)。而这里说的树上背包 Tikck 并没有改变 DP 状态本身，只是证明了朴素合并的总复杂度是 O(n^2)，两者不是一个层面的东西。

在竞赛里，如果你看到"树上选点、需要合并子树、容量可达 n"这类题，第一反应应该是写这个标准树上背包并把复杂度分析写在草稿纸上。如果 m 相对 n 很小，直接享受 O(n*m)。如果 m 和 n 同阶，就用 O(n^2) 这个结论去估算时限。比如 n=5000，O(n^2) 就是 2.5e7 级别，C++ 完全能过；而如果你写成 O(n^3) 的朴素版本就是 1.25e11，铁定超时。

4.3 一个常被忽略的陷阱：父子顺序和 dfs 方向

树形DP要求先递归处理儿子，再合并当前节点。如果你先合并再递归，儿子的dp还没算出来，合并就是拿空状态去更新，答案全错。这个问题在递归版代码里不太会出现，但有人改成迭代栈写的时候容易把顺序搞反。

另外，如果题目没有保证根是 1，你还需要先做一个无向树的 DFS 定根，把父子的方向固定下来。有些题给的"依赖关系"本身就有方向，你存边的时候只存父到子的单向边，那就不需要定根了，直接从那棵树的根开始递归即可。

5. 现场调试与常见问题排查实录

5.1 我遇到过的四个典型问题

这里列一个速查表，都是我自己和带训练时真实踩过的坑。

第一个问题最隐蔽的地方在于：如果树只有一条链，正序循环有时候恰好能过小数据，甚至某些随机数据答案也不容易看出问题。因为链上每个节点只有一个儿子，正序更新的错误会被后续合并"掩盖"一部分。我用链式树和小规模对拍才抓到这个问题。所以我的建议是防患于未然：宁可多复制一个 old 数组，也不要赌自己倒序一定写对。

第二个问题我印象很深。有次写"选课"模板，把整个 dp 数组初始化为 0，然后只在dp[u][1] = val[u]的地方赋值，看起来没问题，但一旦出现负价值，所有状态都从 0 转移，答案全错。后来我把所有非法状态初始化成-INF，只把dp[u][0] = 0、dp[u][1] = val[u]设好，再也没出过这种问题。

5.2 如何验证你的复杂度上界是真的

写完树上背包后，想验证它到底是不是 O(n^2)，不要只看大样例的跑时。我常用的办法是生成一条链树和一棵完全二叉树的随机数据，分别统计总枚举次数。可以在合并的双重循环里放一个计数器：

long long cnt = 0; // 在两层循环内部加一行 cnt += 1;

跑完后打印 cnt。如果 n=5000 且 m=n，cnt 应该在 1e7 级别，而不是 1e10 级别。用这个办法可以快速确认你的循环上限是否裁剪干净。我见过有人的代码在链上退化到了 O(n^3)，本质就是 i 循环没受sz[u]限制，导致每个节点都枚举了接近 m^2 次。

5.3 对拍时的注意事项

树上背包写完之后，最稳的验证方式是和小数据暴力对拍。暴力的写法很简单：枚举所有大小为 m 的节点集合，检查是否满足"选了儿子必须先选父亲"，然后比较答案。n 不超过 15 时这个暴力完全可行。对拍时随机树和随机容量都来一遍，能覆盖到大部分初始化问题。

我个人的习惯是先跑 n=10 的随机树 1000 组，再跑 n=100、m 随机的小数据，最后跑 n=5000 的链看时间。三步都过了，基本可以放心提交。

5.4 最后一个性能小技巧

如果你已经把复杂度剪到了 O(n^2)，但常数还是太大，可以考虑把二维数组的第二维只开到min(m, sz[u]) + 1。比如用vector<vector<int>> dp(n + 1, vector<int>(min(m, n) + 2, -INF))。这样不仅省内存，还能提高缓存命中率。因为树上背包的枚举是顺序访问数组前几个位置，紧凑的内存布局比稀疏大数组快很多。实测在 n=5000、m=5000 的数据上，紧凑数组比全局N*N数组快了将近一倍。

另外，如果你把所有min(m, ...)的计算提出来放在循环外，也能省一点时间。虽然这不是复杂度量级上的优化，但在正式比赛里，这种一次性的小优化往往决定了你是 1.2 秒过还是 1.8 秒卡线。

最后再分享一个实战小技巧：很多树形 DP 题目会把根设成 1，但有些会把依赖关系反着给，你会拿到"每个节点父亲是谁"的数组。这时候不要急着建双向边，先想清楚题目里选的方向是从上到下还是从下到上。如果是"选父才能选子"，直接按父亲数组建单向边，从根往下递归就够了。如果是"选子才能选父"，可以建反向边再设一个超级根。方向一旦反了，树上背包的整个转移都会失效，而且对拍时还很难发现，因为小数据下很多非法方案恰好不会被枚举到。这个坑我踩过一次之后，现在每次写树上背包，第一件事就是确认依赖方向。