1. 树上背包的复杂度疑问从哪里来如果有人问我算法竞赛里最像魔术的一个复杂度结论是什么我会说是树上背包的合并操作明明每个节点都要把儿子子树合并进来每次合并又是一层接近 O(n^2) 的枚举为什么算出来总复杂度不是 O(n^3)而是 O(n^2)这个问题我当年第一次接触时也卡了很久。后来带学弟学妹训练发现几乎每个人都会在这个Trick上纠结一遍。所以这篇文章就把这个Trick 树上背包合并复杂度分析完整拆开从直觉误区、证明方式、代码实现到调试经验一次讲透。适合刚学树形DP、准备竞赛或者想彻底搞懂树上背包复杂度的同学。先明确我们讨论的问题长什么样。最常见的模板是选课问题给定一棵树每个节点有一个价值选一个点之前必须选它的父亲最多选 m 个点问最大总价值。经典做法是用树形DPdp[u][k]表示在 u 的子树里选 k 个点并且 u 已经被选中时的最大价值。转移的时候要把 u 的每个儿子 v 的子树当成一组待合并的物品像普通背包那样滚进去。这时候一眼看过去每个节点都要枚举 i 和 j两重循环外面再套一层 DFS复杂度怎么想都像 O(n^3)。很多初学者就在这里开始怀疑人生这么简单的转移难道真的有三重循环其实三重循环确实有但第三层循环不是凭空多出来的 n合在一起反而被限制住了。关键就在于合并这两个字上。要理解这个复杂度结论不能站在节点数 × 背包容量的角度去乘而要站在合并次数的角度去看。接下来我会先给一个直观证明再给一份可以直接抄的代码最后讲一些我自己踩过的坑。2. 复杂度上界的直观证明每个点对只相遇一次2.1 把一次合并拆开看先看标准转移代码里的一次合并。假设当前处理到 u已经合并完了一部分儿子这部分总大小为a现在要把儿子 v 合并进来v 的子树大小为b。合并时做的事是枚举 i 从 1 到 aj 从 1 到 b然后尝试用dp[u][i] dp[v][j]更新dp[u][ij]。这一轮合并的枚举次数就是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]; vectorint 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][ij]更新完之后后面的循环又可能拿这个新值去更新更大的容量相当于把同一棵子树的物品用了多次。初学者最常见的错误就是这里写成正序最后答案偏大又查不出原因。第三个细节是 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][ij]。这样不管 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) 这个结论去估算时限。比如 n5000O(n^2) 就是 2.5e7 级别C 完全能过而如果你写成 O(n^3) 的朴素版本就是 1.25e11铁定超时。4.3 一个常被忽略的陷阱父子顺序和 dfs 方向树形DP要求先递归处理儿子再合并当前节点。如果你先合并再递归儿子的dp还没算出来合并就是拿空状态去更新答案全错。这个问题在递归版代码里不太会出现但有人改成迭代栈写的时候容易把顺序搞反。另外如果题目没有保证根是 1你还需要先做一个无向树的 DFS 定根把父子的方向固定下来。有些题给的依赖关系本身就有方向你存边的时候只存父到子的单向边那就不需要定根了直接从那棵树的根开始递归即可。5. 现场调试与常见问题排查实录5.1 我遇到过的四个典型问题这里列一个速查表都是我自己和带训练时真实踩过的坑。现象主要原因解决方案答案比正确答案大i 循环写了正序同一棵子树被重复使用改成倒序或用 old 临时数组复制旧状态答案比正确答案小dp[u][0]被错误初始化为负无穷合法状态缺失把dp[u][0]设为 0dp[u][1]设为val[u]O(n^3) 超时i 或 j 的循环上限没裁剪到min(m, sz)写i min(m, sz[u])j min(m - i, sz[v])内存爆炸开了dp[n1][m1]但 m 也接近 n且多个 dfs 复用大数组用vectorvectorint按需分配或改用 old 数组滚动优化第一个问题最隐蔽的地方在于如果树只有一条链正序循环有时候恰好能过小数据甚至某些随机数据答案也不容易看出问题。因为链上每个节点只有一个儿子正序更新的错误会被后续合并掩盖一部分。我用链式树和小规模对拍才抓到这个问题。所以我的建议是防患于未然宁可多复制一个 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。如果 n5000 且 mncnt 应该在 1e7 级别而不是 1e10 级别。用这个办法可以快速确认你的循环上限是否裁剪干净。我见过有人的代码在链上退化到了 O(n^3)本质就是 i 循环没受sz[u]限制导致每个节点都枚举了接近 m^2 次。5.3 对拍时的注意事项树上背包写完之后最稳的验证方式是和小数据暴力对拍。暴力的写法很简单枚举所有大小为 m 的节点集合检查是否满足选了儿子必须先选父亲然后比较答案。n 不超过 15 时这个暴力完全可行。对拍时随机树和随机容量都来一遍能覆盖到大部分初始化问题。我个人的习惯是先跑 n10 的随机树 1000 组再跑 n100、m 随机的小数据最后跑 n5000 的链看时间。三步都过了基本可以放心提交。5.4 最后一个性能小技巧如果你已经把复杂度剪到了 O(n^2)但常数还是太大可以考虑把二维数组的第二维只开到min(m, sz[u]) 1。比如用vectorvectorint dp(n 1, vectorint(min(m, n) 2, -INF))。这样不仅省内存还能提高缓存命中率。因为树上背包的枚举是顺序访问数组前几个位置紧凑的内存布局比稀疏大数组快很多。实测在 n5000、m5000 的数据上紧凑数组比全局N*N数组快了将近一倍。另外如果你把所有min(m, ...)的计算提出来放在循环外也能省一点时间。虽然这不是复杂度量级上的优化但在正式比赛里这种一次性的小优化往往决定了你是 1.2 秒过还是 1.8 秒卡线。最后再分享一个实战小技巧很多树形 DP 题目会把根设成 1但有些会把依赖关系反着给你会拿到每个节点父亲是谁的数组。这时候不要急着建双向边先想清楚题目里选的方向是从上到下还是从下到上。如果是选父才能选子直接按父亲数组建单向边从根往下递归就够了。如果是选子才能选父可以建反向边再设一个超级根。方向一旦反了树上背包的整个转移都会失效而且对拍时还很难发现因为小数据下很多非法方案恰好不会被枚举到。这个坑我踩过一次之后现在每次写树上背包第一件事就是确认依赖方向。