树形DP很多地方也写成树状dp在我眼里是算法里少有的一旦开窍就再也不会忘的东西。它的内核其实只用一句话就能概括在树上做自底向上的状态合并。但真到了写题的时候卡住大多数人的从来不是转移方程本身而是前面那几步——状态怎么定义、复杂度为什么是那个数、答案不在根上的时候怎么办、递归爆栈了怎么改。这几年我带过不少人啃树形dp发现同一个人把最大独立集写熟之后遇到换根DP还是会翻车遇到树上背包还是会写成 O(n³)。所以这篇不打算再复述一遍教材上的定义而是按我自己的理解顺序把树形dp拆成几件真正需要动手的事来讲从状态设计一路讲到调试排查代码都用 C 写能直接抄去改。1. 树上问题为什么天然适合自底向上1.1 从一个具体的小问题入手先别急着谈状态转移这些词。拿一个最朴素的题感受一下给一棵 n 个点的树每个点有个权值要求选出若干个点选出的点之间不能有边相连问最大权值和是多少。这个问题叫树上最大权独立集是树形dp最经典的入门形态。你可能会想暴力枚举所有点选或不选2ⁿ 种情况n 稍微大一点就废了。但树这个东西有个很好的性质——它没有环任意一条边断开都会把树分成两半而这两半之间唯一的联系就是这条边本身。也就是说如果我从叶子往上考虑每个点只需要关心我的子节点选没选这一件事完全不用管远处的点怎么选。这就是自底向上能成立的物理直觉。把这个直觉翻译成代码就是两个数组dp[u][0] 表示以 u 为根的子树里、不选 u 的情况下的最大权值和dp[u][1] 表示选了 u 的情况下的最大权值和。转移逻辑不说自明如果我选了 u那所有儿子都不能选只能取 dp[v][0]如果我不选 u每个儿子选或不选都合法取两者的较大值。#include bits/stdc.h using namespace std; const int N 1e5 5; vectorint g[N]; int val[N]; long long dp[N][2]; void dfs(int u, int fa) { dp[u][1] val[u]; dp[u][0] 0; for (int v : g[u]) { if (v fa) continue; dfs(v, u); dp[u][1] dp[v][0]; dp[u][0] max(dp[v][0], dp[v][1]); } } int main() { // 建图、读权值略 dfs(1, 0); printf(%lld\n, max(dp[1][0], dp[1][1])); return 0; }这段代码短得有点不像话但它已经把树形dp的全部骨架都摆出来了递归下去把子问题算完回到当前点时把子问题的答案按规则合并。真正需要动脑的地方从来都在按什么规则合并上。1.2 递归序本身就是执行顺序有一个点很多人没意识到树形dp的求解顺序和普通的线性dp不一样。数组dp不是按下标从小到大填的而是按后序遍历的顺序填的。dfs 函数在进入 u 之后先对所有子节点递归等每个子节点都返回了才开始算 dp[u]。这意味着在写 dp[u] 那两行的时候所有儿子的 dp 值一定是最终值绝对不会出现用到还没算完的状态这种事。这一点决定了手写树形dp时的一个硬规则合并儿子的循环必须写在递归调用之后不能提前。我见过有人为了先统计一下子树大小把循环拆开结果顺序一乱整个dp就崩了。顺便说一个常见误会。很多教材把树形dp写成从叶子节点开始递推给人一种要先把叶子挑出来排序的印象。实际上你不需要显式地排序递归调用栈自动帮你做了这件事。真到了递归爆栈要改成迭代的时候才需要手工去构造这个后序顺序那是后话。1.3 它和线性dp的分水岭线性dp的状态转移是从前往后或者从小范围往大范围状态之间存在一个天然的偏序。树形dp的状态之间存在的偏序是父子关系儿子的状态必须先于父亲算完。这就是全部区别。所以判断一个问题能不能用树形dp看两件事就够了第一问题的结构是不是树或者可以转化成树比如基环树的环上拆边第二一个点的答案能不能只靠它子树的信息拼出来。第二条比第一条更容易踩雷因为有很多树上问题光靠子树信息是不够的——这时候要么加状态维度要么上换根DP要么干脆换算法点分治、树上莫队之类。提示如果一个树上问题的答案需要跨过某个点往上走再拐下来别急着往树形dp里硬塞状态先想想是不是换根DP或者路径统计的活。2. 状态设计落笔之前先想清楚我要记住什么2.1 状态里挂当前点选没选最简单的一类状态就是当前点是否被选中最大独立集就是典型。它的本质是把约束拆成局部可见的形式题目说相邻两点不能同时选我只要在合并儿子的时候检查这条边就够了不需要记住整条路径。顺着这个思路还能延伸出不少变体比如相邻两点不能同时不选最小支配集的弱化版、相邻两点颜色不同树的二染色、每个点有 k 种颜色且相邻不能同色。这些问题的共同点是约束只涉及一条边上的两个端点所以状态里只需要挂当前点的选择即可。但一旦约束跨过两条边、三条边比如距离为 2 的点不能同色状态就不能只记自己了还得记住父亲的染色情况。这就是状态维度膨胀的起点。2.2 状态里挂容量树上背包第二种常见形态是把一个数值型的量挂进状态。典型的就是树上背包给一棵树每个点有重量 w 和价值 v选一个点必须先选它的父亲问容量为 m 时能拿到的最大价值。这里的 dp[u][j] 表示在 u 的子树里选 j 个点且选了 u的最大价值。转移就是在合并儿子的时候做一次卷积式的枚举int sz[N]; long long dp[N][M]; // 注意 M 不要开太大下面会讲 void dfs(int u, int fa) { sz[u] 1; for (int j 0; j m; j) dp[u][j] -INF; dp[u][1] val[u]; for (int v : g[u]) { if (v fa) continue; dfs(v, u); int up min(sz[u], m); for (int j up; j 1; --j) { if (dp[u][j] -INF) continue; int lim min(sz[v], m - j); for (int k 1; k lim; k) { if (dp[v][k] -INF) continue; dp[u][j k] max(dp[u][j k], dp[u][j] dp[v][k]); } } sz[u] sz[v]; } }这段代码里藏了两个细节都是踩过坑才记住的。第一j必须从大到小枚举因为 dp[u][jk] 会覆盖到比 j 大的位置从小到大枚举会导致同一个儿子被重复选。第二k的上界要卡成min(sz[v], m - j)不能无脑写成 m否则复杂度会白白多一个量级。2.3 状态里挂正在走的这条链第三种形态是路径类问题。求树的直径是最典型的例子dp[u] 表示从 u 往下走的最长路合并儿子的时候顺手更新一下全局答案。int down[N], diam 0; void dfs(int u, int fa) { down[u] 0; for (int v : g[u]) { if (v fa) continue; dfs(v, u); // 先算跨过 u 的两条链拼接再更新 down[u] diam max(diam, down[u] down[v] 1); down[u] max(down[u], down[v] 1); } }注意这两行的顺序不能反。先更新 diam 时用的是之前已经处理过的兄弟子树里的最长链再加上当前子树的最长链拼成一条穿过 u 的路径如果先把 down[u] 更新了就会变成同一条链自己和自己拼接答案直接虚高。这类边遍历子节点边更新全局最优的写法在路径统计里非常常见本质上是把经过 u 的所有路径按由哪个儿子提供另一端点分了类不多不少正好枚举一遍。2.4 状态维度失控前的三个预警状态设计最容易犯的错误是维度越加越多最后写出一个 dp[u][i][j][k] 然后自己都理不清转移。我一般用三个信号来判断是不是跑偏了状态里出现了依赖子树外信息的量比如整棵树里选了几个那说明该用换根或者该用别的算法两个维度之间存在明显的冗余比如 j 恒等于 sz[u]那就不该单独立一维转移时需要回退某个已合并的贡献比如去掉某个儿子之后重新算这通常意味着要从树形dp换成换根DP或者按边贡献单独统计。我个人经验如果一个树形dp的状态超过两维先把题目重新读一遍八成是漏掉了某个能让你只记子树信息的性质。3. 复杂度账本为什么有人写出来是 O(n²)有人是 O(n³)3.1 合并两个子树到底枚举了多少次树上背包那段代码外层两层循环看起来非常吓人很多人第一反应是 O(n³) 甚至更高。但实际分析下来并不是这样。关键在于每一对点 (a, b)只在它们的 LCA 处被枚举一次。合并儿子 v 到 u 的时候我们枚举的是从 u 的已处理子树里选 j 个和从 v 的子树里选 k 个的所有组合这些组合的实质就是一端在已处理子树、一端在 v 子树里的点对。每个点对只会被它所在的那对子树枚举一次而这两个子树的根恰好在同一层合并也就是它们的 LCA 处。所以总的枚举次数是 O(n²)而不是 O(n³)在第二维不限容量的情况下。如果第二维被限制在 m 以内那么每个点对至多贡献 m 次状态整体复杂度是 O(n·m)。这个结论在树上背包类题目里非常实用因为它告诉你可以放心地把容量开到几万只要 n·m 在可接受范围内。3.2 卡上界带来的实际差距上面的分析是理论值实际跑起来还有一层你有没有真的把上下界卡紧。如果外层 j 从 m 开始枚举、内层 k 也老老实实从 1 枚举到 m那么即使逻辑正确常数也会大得离谱。正确的姿势是外层 j 上界取 min(sz[u], m)内层 k 上界取 min(sz[v], m - j)同时下界也可以优化比如 j 至少为 1。再进一步如果你确定某棵子树的点数少于 m那么在处理它的时候完全可以只枚举到 sz[v]避免大量无效的 -INF 状态运算。我做过对比测试同样一份逻辑卡不卡上界在小数据上差别不明显但 n 到 5000、m 到 5000 的时候差距能到 3 倍以上。3.3 那些不算进复杂度但拖慢程序的东西复杂度对了不代表跑得快。树形dp常踩的几个常数坑隐患表现处理方式vector 邻接表反复扩容建图阶段抖动预先 reserve或者用前向星每次递归都 memset 大数组时间全花在清零上只清零用到的范围或用时间戳标记dp 数组按 n×m 开内存超限改成滚动数组或按子树大小动态开递归调用本身的开销深树上明显小规模改迭代或加编译优化特别是第三行。dp[N][M] 这种开法在 n m 5000 的时候就是 2500 万个 long long两百兆内存直接起飞。常见的处理办法是给每个点动态分配一个大小为 sz[u]1 的 vector或者用树上背包经典的儿子向父亲复用空间的写法。4. 换根DP当答案不在根上4.1 两次DFS的分工有一类问题问的是每个点作为起点或者作为根时的某个答案比如每个点到其它所有点的距离之和每个点作为根时的最小深度和。这类问题如果对每个点都单独跑一遍DFS复杂度直接 O(n²)。换根DP的思路是用两次线性DFS把它压到 O(n)。第一次DFS以任意点通常取1为根求出每个点的子树信息比如子树大小 sz[u]、子树内所有点到 u 的距离和 down[u]。第二次DFS从上往下走利用父亲已经算好的全局答案推出儿子的答案。4.2 完整走一遍每个点到所有点的距离和先看第一次DFS。down[u] 表示 u 的子树内所有点到 u 的距离之和long long sz[N], down[N], f[N]; int n; void dfs1(int u, int fa) { sz[u] 1; down[u] 0; for (int v : g[u]) { if (v fa) continue; dfs1(v, u); sz[u] sz[v]; down[u] down[v] sz[v]; // v 子树每个点到 u 都要多走一步 } }down[v] sz[v]这一项的含义是v 子树内的每个点到 u 的距离等于它到 v 的距离再加 1所以总共多出 sz[v]。第二次DFS要解决的问题是已知 f[u]所有点到 u 的距离和怎么求 f[v]。把整棵树按v 的子树和其余部分切开从 u 走到 v 时v 子树里的 sz[v] 个点各自少走一步其余 n - sz[v] 个点各自多走一步所以f[1] down[1]; void dfs2(int u, int fa) { for (int v : g[u]) { if (v fa) continue; f[v] f[u] - sz[v] (n - sz[v]); dfs2(v, u); } }化简一下就是f[v] f[u] n - 2 * sz[v]。这个式子非常漂亮也很好记每往下一个点整体距离和的变化等于 n - 2·sz[v]。当 sz[v] 超过 n/2 时这个变化是负的也就意味着重心方向的答案更小这其实顺手也就把树的重心求出来了。4.3 换根时最容易出错的两个地方第一个坑是忘了方向。dfs2 里递推 f[v] 用到的 sz[v] 是v 作为子节点时的子树大小这个值在第一次DFS里是以1为根算的方向是对的。但如果你把换根逻辑套在别的量上比如子树内最大深度那就要小心了从 u 推到 v 的时候v 这一侧的信息变了你得重新算一遍u 去掉 v 这棵子树之后的最深链这往往需要维护最大值和次大值。我见过太多人在这里直接拿 max 一减结果减掉的是别的儿子的贡献。第二个坑是根节点的初值。f[1] 必须先用第一次DFS的结果填上也就是 down[1]不能想当然地写 0。这个错误在小样例上很容易被掩盖因为 n 小的时候结果看起来差不多。我自己的习惯是换根DP写完先手算 n 3 的一条链看看三个点的答案是不是 3、2、3。这个例子能同时验证初值、方向、递推式三件事。5. 把递归改写成迭代深度上万之后的必修课5.1 手工栈构造后序序列树退化成链的时候n 到十万级递归基本必爆。改迭代的第一步是构造一个父亲已知、且能倒序处理的节点序列int fa[N], order[N], cnt 0; void build_order(int root) { stackint st; st.push(root); fa[root] 0; while (!st.empty()) { int u st.top(); st.pop(); order[cnt] u; for (int v : g[u]) { if (v fa[u]) continue; fa[v] u; st.push(v); } } } // 主逻辑倒序遍历保证儿子先于父亲 void solve() { for (int i cnt; i 1; --i) { int u order[i]; // 此处 dp[u] 的初始值 for (int v : g[u]) { if (v fa[u]) continue; // 合并 dp[v] 到 dp[u] } } }这个写法的原理是栈式遍历保证了任何一个点在 order 中的位置一定晚于它的父亲因为父亲先入 order 才轮到儿子。所以把 order 倒过来就是标准的后序——儿子永远在父亲前面被处理。逻辑和递归版本一模一样只是把调用栈换成了显式数组。5.2 什么时候可以偷懒用BFS序如果你的转移只依赖儿子已经算完这一个条件而且每个点的状态只需要被父亲读一次那么其实用普通的 BFS 顺序加倒序遍历就足够了上面的写法完全可以胜任。但如果你需要在处理 u 的时候同时访问所有已经处理完的儿子以某个顺序排列那就得额外维护儿子列表简单点说就是别用 vector 存临时结果直接原地合并。5.3 空间上的自适应迭代写法的另一个好处是方便做内存控制。递归版本里每一层栈帧都持有局部变量深树上内存占用会明显上升。改成迭代之后你可以按需分配dp[u] 用 vector 按 sz[u]1 开处理完之后如果确定不再需要比如只算一次答案可以直接释放。树上背包用这种方式能把峰值内存压下来不少。代价是代码会变长、可读性下降。所以我的取舍原则是n 在 2×10⁴ 以内、且比赛环境允许开大栈就用递归超过这个量级或者题目明确给了深链数据直接上迭代别纠结。6. 写挂了怎么查一份可复用的排查链路6.1 先把树本身验证掉树形dp出问题有相当一部分根本不是dp写错了而是树建错了。最常见的三种加了双向边但没判父亲导致死循环节点编号从 0 开始却把 0 当成了没有父亲的哨兵多组数据没有清空邻接表。验证方法很土但很有效加一段代码统计cnt从根出发能访问到的点数如果它不等于 n直接说明建图或者遍历出了问题不用往下查dp了。// 调试用确认遍历覆盖了所有点 assert(cnt n); // 调试用输出每个点的 sz 与深度 for (int i 1; i n; i) printf(%d: sz%d dep%d\n, i, sz[i], dep[i]);6.2 对拍是最省时间的办法树形dp的状态转移逻辑很容易出边界错误靠盯着看是看不出来的。写一个 O(2ⁿ) 的暴力n ≤ 18 时把点集全部枚举一遍随机生成小树对拍通常几分钟就能抓到反例。我一般会固定几个特殊形状去测纯链、纯菊花一个中心连着所有点、随机树、两个点。这四种形状几乎覆盖了所有根节点特殊深度极端儿子数量极端的边界情况。对拍脚本不需要写得多精致能跑就行for i in $(seq 1 500); do python3 gen.py in.txt ./bf in.txt out1.txt ./sol in.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo WA on case $i; break fi done6.3 常见错误对照表现象大概率原因定位方式答案偏大兄弟子树被重复合并或路径问题里先更新了 down手算 n3 的链看答案答案偏小dp 初值没设对或 -INF 参与运算溢出打印每个点的 dp 状态部分点答案为 0该点没被遍历到或 dp 数组没清统计访问点数大规模 RE递归爆栈或数组开小了看崩溃点改迭代复杂度超时没卡上界或 memset 太频繁加计数器统计循环次数最后一行那个加计数器的技巧我特别推荐。在双重循环里放一个cnt_inner跑一组大数据看看实际枚举了多少次。如果它远超 n²那说明上界卡错了如果它只有几千但你却超时了那瓶颈一定在别处。这比凭感觉猜要靠谱得多。写到这里我还想补一个自己踩过的坑。有一次做一道树上依赖背包容量 m 开到了 30000n 有 2000理论上 n·m 是六千万感觉能过。结果一直 TLE查了半天发现是 dp 数组用了long long dp[N][M]的静态开法一千万个 long long 光清零就花了不少时间而且缓存局部性极差。后来改成按子树大小动态分配、并且用 int 存价值确实没超 int 范围时间直接掉到原来的四分之一。所以树形dp这东西转移方程写对只算及格把常数和内存一起管住才算真的写完了。