树形DP入门：从状态定义到子树合并的完整指南

1. 从一道“没有思路”的题说起树形DP到底在解决什么如果你刷过一定量的算法题大概率会遇到这样一类场景给出一棵有根树每个节点有自己的权值要求你在树上选一些节点使得选出的节点满足某种约束比如父子不能同时选、覆盖所有边、路径和最大等并求出最优值。第一次碰到这种题很多人的第一反应是“这怎么用DP状态怎么定义转移从哪来”——我当年也是这样盯着题目看了半小时连状态都写不出来。树形DP说白了就是把动态规划这件事搬到树这种数据结构上做。它之所以让人一开始摸不着头脑是因为我们习惯的线性DP是“一条线”上递推而树是分叉的一个节点可能有多个孩子转移的时候要同时考虑所有子树。但一旦你理解了它的核心思想——把每棵子树当成一个独立的子问题先算子树的最优解再合并到父节点——这类题就会变得有章可循。这篇文章适合谁看如果你已经会写基础的线性DP比如背包、最长上升子序列但对树上问题总是无从下手那这篇就是写给你的。我会从“为什么树形DP要这样设计状态”讲起把状态定义、转移方程、遍历顺序、边界处理这些关键环节一个个拆开再配合几道经典模型的完整代码和踩坑记录让你看完能直接上手写题。关键词里提到的“树形DP”“动态规划”“子树合并”“后序遍历”这些概念我都会在具体场景里解释清楚不堆术语。先说一个我自己的教训。刚学树形DP的时候我最大的误区是“想一次性把整棵树的状态都想清楚”结果越想越乱。后来才明白树形DP的正确打开方式是递归思维你只需要想清楚“以某个节点为根的子树它的最优解怎么由它的孩子们的子树最优解推出来”剩下的交给递归。这个思维转变是我觉得学树形DP最关键的一步。2. 树形DP的状态定义为什么“以u为根的子树”是万能切入点2.1 树的结构天然适合递归子问题就是子树树有一个非常好的性质任意一个节点u把它和它的所有后代拿出来本身又是一棵树。这意味着如果我们定义“以u为根的子树”为一个子问题那么这个问题可以完全独立地求解不需要关心u的祖先是谁、兄弟是谁。这就是树形DP能够成立的根本原因。对比一下线性DP线性DP里dp[i]表示“前i个元素的最优解”子问题是前缀。树上没有“前缀”这种线性顺序但有“子树”这种嵌套结构。所以树形DP的状态几乎总是长这样dp[u][...]表示以u为根的子树在某种状态下的最优值。那个“...”是附加的状态维度取决于题目约束。举个最经典的例子没有上司的舞会也常叫“树的最大独立集”。题目是每个节点有一个快乐值选一些节点要求选了某个节点就不能选它的父节点求最大快乐值总和。这里的状态就是dp[u][0]表示“不选u时以u为根的子树的最大值”dp[u][1]表示“选u时以u为根的子树的最大值”。为什么是这两个状态因为u选不选直接决定了它的孩子们能不能选这个信息必须传递给子树。2.2 状态维度怎么定看“父节点需要知道子树的什么信息”很多人卡在状态定义上不知道该开几维、每维表示什么。我的经验是问自己一个问题——父节点在合并子树时需要从子树知道哪些信息这些信息就是状态维度。还是拿“没有上司的舞会”举例。父节点u在决定自己选不选的时候需要知道孩子v“选v时的最优值”和“不选v时的最优值”。所以孩子必须把这两个值都算出来给父节点状态就是二维的。如果题目再加一个约束比如“每个节点有一个花费总花费不能超过K”那父节点还需要知道“花费为k时的最优值”状态就变成dp[u][j][0/1]其中j是花费。维度是随着约束增加的。这里有个容易犯的错误状态开太多维导致复杂度爆炸。比如有的题你可能会想“我要记录子树里选了几个节点”于是开dp[u][cnt]结果复杂度变成O(n^2)甚至更高。这时候要判断这个维度是否真的必要能不能用其他方式优化比如树上背包的上下界优化。我见过不少人在树上背包问题上因为没做上下界优化而超时这个后面会专门讲。2.3 一个反直觉的点状态不一定从叶子往上“算”而是从根往下“需要”初学者容易有一个误解树形DP是从叶子节点开始一层层往上算。这个说法方向是对的但理解上容易偏。更准确的说法是我们从根节点开始递归递归到叶子时自然得到叶子的状态然后在回溯的过程中合并。也就是说代码的调用顺序是从根往下但状态的求解顺序是从叶子往上。这个“调用顺序”和“求解顺序”的区分很重要因为它决定了你写递归函数时的思路。我习惯的写法是写一个dfs(u, parent)函数先递归所有孩子再处理u自己的状态合并。这样代码结构非常清晰孩子没算完我不动u。这也是为什么树形DP几乎都用后序遍历先孩子后自己的原因。3. 转移方程的推导合并子树时的三种典型模式3.1 模式一父子约束型——选或不选的二元决策这是最简单也最常见的一类。代表题就是“没有上司的舞会”。转移方程长这样dp[u][0] Σ max(dp[v][0], dp[v][1])对所有孩子v求和dp[u][1] val[u] Σ dp[v][0]对所有孩子v求和为什么dp[u][0]里孩子v可以选也可以不选因为u没选对v没有约束v选不选都行取最大值。为什么dp[u][1]里孩子v只能不选因为u选了v作为孩子不能选所以只能加dp[v][0]。这个逻辑非常直白但它是所有父子约束型树形DP的模板。我刚开始写的时候总是忘记dp[u][1]要加上val[u]本身或者忘记dp[u][0]要对孩子取max。这两个点是最容易出错的。建议写完之后手动模拟一棵三层的小树验证一下转移对不对。3.2 模式二背包合并型——子树之间做资源分配这类题的典型场景是每个节点代表一个物品有体积和价值选了一个节点就必须选它的父节点依赖背包总容量有限求最大价值。这时候状态是dp[u][j]表示“以u为根的子树在容量j下的最大价值”。转移的时候u的每个孩子v相当于一组物品要在u的容量里分配一部分给v的子树。转移方程的核心是一个类似背包的合并过程for each child v of u: for j from size_u down to 0: for k from 0 to j: dp[u][j] max(dp[u][j], dp[u][j-k] dp[v][k])这个三重循环看起来和普通背包一样但复杂度分析很关键。如果直接写复杂度是O(n * K^2)其中K是容量。但树上背包有一个经典优化每个子树的大小作为循环上界这样总复杂度可以降到O(n * K)。这个优化我第一次看到的时候觉得很神奇后来自己推了一遍才明白因为每个点对只会在它们的LCA处被合并一次总的合并次数是O(n)级别的。这里有个坑循环顺序必须是倒序和01背包一样。如果正序就会重复选同一个孩子子树里的物品。我见过有人写成正序结果答案偏大debug了半天。3.3 模式三路径统计型——维护子树内的某种信息这类题不是“选或不选”而是统计树上满足条件的路径数量或者求最长路径。典型的是“树的直径”和“树的重心”相关问题。以树的直径为例状态是dp[u]表示“从u出发往下的最长路径长度”。转移的时候对于每个孩子vdp[u] max(dp[u], dp[v] 1)。但直径不一定经过根所以还要在合并的过程中记录“经过u的最长路径”也就是取孩子中最大的两个dp[v] 2。这类题的关键在于答案不一定在根节点的状态里而是在合并过程中产生的。所以你需要一个全局变量ans在每次合并孩子的时候更新。我一开始总是忘记更新ans只返回了dp[u]结果答案永远是0或者某个不对的值。4. 遍历顺序与实现细节递归、迭代、还是拓扑排序4.1 递归写法最直观但要注意栈深度树形DP最自然的写法就是递归。伪代码大概是这样def dfs(u, parent): # 初始化dp[u] for v in children[u]: if v parent: continue dfs(v, u) # 合并v的dp到u # 处理u的最终状态这个写法清晰易懂但有一个隐患递归深度。如果树是一条链深度达到nPython默认递归深度是1000n超过1000就会爆栈。C一般没问题但Python需要手动设置sys.setrecursionlimit。我一般会设成n 10或者1000000保险起见。另一个细节是parent参数的传递。因为树是无向的你需要避免走回父节点。有两种写法一种是传parent参数另一种是建图的时候只建有向边从父到子。前者更通用后者需要你先确定根。我一般用前者因为不需要额外处理。4.2 迭代写法手动模拟栈避免递归限制如果不想用递归可以用栈手动模拟后序遍历。思路是先做一次DFS得到每个节点的父节点和访问顺序然后按逆序处理。或者用两个栈模拟后序。这个写法代码量大一些但不受递归深度限制。我在处理n特别大的题目时会用这种写法。还有一种更简单的迭代方式先做一次BFS得到拓扑序从根到叶然后逆序处理。因为树本身就是一个DAG逆序处理就能保证孩子先于父节点被处理。这个写法我觉得比手动模拟栈更清晰推荐大家试试。4.3 建图方式邻接表还是链式前向星对于树形DP建图方式影响不大因为每个节点只会被访问一次。邻接表vector数组写起来最方便C里就是vectorint g[N]。链式前向星在竞赛里更常见因为速度快但写起来麻烦一些。如果是平时练习我建议用邻接表代码可读性高。如果是比赛看个人习惯两者都能过。有一个小细节如果题目给的是有根树直接告诉你根是谁你可以只建有向边省掉parent判断。如果给的是无向树就必须建双向边。我一般统一建双向边然后用parent参数控制这样不容易出错。5. 经典模型实战从“没有上司的舞会”到“树上背包”5.1 没有上司的舞会树形DP的Hello World这道题我做过不下十遍每次复习树形DP都从它开始。题目描述很简单n个节点每个节点有权值选一些节点父子不能同时选求最大权值和。状态定义dp[u][0]和dp[u][1]。 转移上面已经写过。 边界叶子节点的dp[u][0] 0dp[u][1] val[u]。 答案max(dp[root][0], dp[root][1])。完整代码Pythonimport sys sys.setrecursionlimit(1000000) def solve(): n int(input()) val [0] * (n 1) for i in range(1, n 1): val[i] int(input()) g [[] for _ in range(n 1)] has_parent [False] * (n 1) for _ in range(n - 1): u, v map(int, input().split()) g[v].append(u) has_parent[u] True root 1 for i in range(1, n 1): if not has_parent[i]: root i break dp [[0, 0] for _ in range(n 1)] def dfs(u): dp[u][1] val[u] for v in g[u]: dfs(v) dp[u][0] max(dp[v][0], dp[v][1]) dp[u][1] dp[v][0] dfs(root) print(max(dp[root][0], dp[root][1])) solve()这段代码里我特意用了has_parent数组来找根因为题目给的是有向边从父到子但顺序是乱的。如果题目给的是无向边就需要用parent参数。这个细节很多人第一次做的时候会忽略导致根找错。5.2 树上背包依赖背包的树形版本树上背包的经典题是“选课”n门课每门课有学分选一门课必须先选它的先修课总共选m门求最大学分。这本质上是一个依赖背包依赖关系形成一棵树。状态dp[u][j]表示以u为根的子树选j门课的最大学分。 初始化dp[u][1] 学分[u]选u自己。 转移对每个孩子v做一次背包合并。def dfs(u): dp[u][1] score[u] size[u] 1 for v in g[u]: dfs(v) # 合并v的子树 for j in range(min(size[u], m), 0, -1): for k in range(1, min(size[v], m - j) 1): dp[u][j k] max(dp[u][j k], dp[u][j] dp[v][k]) size[u] size[v]这里的关键是size[u]的维护和循环上界的控制。如果不加size限制复杂度会退化。我实测过n1000、m1000的数据不加优化会超时加了之后秒过。还有一个坑虚拟根节点。因为原图可能是一个森林多棵树所以需要加一个虚拟根0把所有树的根连到0上然后对0做dfs。最后答案是dp[0][m1]因为0本身不算一门课但初始化时dp[0][1]0所以要多选一个。这个技巧很常用值得记住。5.3 树的直径路径统计型树形DP树的直径有两种求法两次BFS/DFS或者树形DP。两次BFS更简单但只能求直径长度不能处理带权边带权边也能做但需要调整。树形DP更通用能处理带权边也能顺便求出直径路径。树形DP求直径的思路对每个节点u维护“从u往下走的最长路径”dp[u]。合并孩子v时用dp[v] w(u,v)更新dp[u]同时用“当前最长次长”更新答案。ans 0 def dfs(u, parent): global ans dp[u] 0 for v, w in g[u]: if v parent: continue dfs(v, u) ans max(ans, dp[u] dp[v] w) dp[u] max(dp[u], dp[v] w)注意ans的更新必须在dp[u]更新之前否则会用到已经更新的dp[u]导致路径重复。这个顺序问题我踩过坑当时答案总是偏大后来发现是顺序反了。6. 复杂度分析与优化为什么你的树形DP会超时6.1 树上背包的上下界优化从O(nK^2)到O(nK)前面提到过树上背包的朴素写法是三重循环复杂度O(nK^2)。但通过限制循环上界为子树大小可以降到O(nK)。这个优化的原理是每一对节点只会在它们的LCA处被合并一次。所以总的合并次数是O(n)级别的每次合并的代价是O(K)总复杂度O(n*K)。具体实现就是上面代码里的min(size[u], m)和min(size[v], m-j)。这两个上界看起来简单但效果非常明显。我做过一个实验n2000m2000的随机树不加优化跑了8秒加了优化0.3秒。差距就是这么大。6.2 状态压缩什么时候可以省掉一维有些题的状态看起来需要三维但实际上可以省掉一维。比如“每个节点选或不选且总花费不超过K”状态是dp[u][j][0/1]。但如果题目只问“最大价值”不要求输出方案那么0/1这一维可以在合并时临时处理不需要一直存着。具体做法是先算dp[u][j][0]和dp[u][j][1]合并完孩子后如果父节点只需要知道“选u”和“不选u”的最大值那就可以把这两组合并成一个数组。这个技巧需要具体题目具体分析不是所有题都能省。我的经验是如果某一维只在当前节点有用不需要传给父节点那就可以省。判断标准就是前面说的“父节点需要知道什么”。6.3 换根DP当答案不在固定的根上有一类题是对于每个节点求以它为根时的某个值。比如“求每个节点到其他所有节点的距离之和”。如果对每个节点都做一次DFS复杂度O(n^2)n大一点就超时。这时候需要用换根DP。换根DP的思路是先以1为根做一次DFS求出dp[1]和每个子树的size。然后再做一次DFS从父节点推到子节点。比如距离之和的换根转移是dp[v] dp[u] n - 2*size[v]。这个公式的推导需要画图理解但记住之后很好用。换根DP是树形DP里比较进阶的内容但面试和比赛中出现频率不低。我建议先把基础的树形DP练熟再碰换根。7. 我踩过的那些坑从RE到WA的完整排查记录7.1 递归爆栈Python选手的必修课第一次用Python写树形DPn10000的链直接RE。报错是RecursionError: maximum recursion depth exceeded。解决办法是sys.setrecursionlimit(1000000)。但设太大也有风险可能真的把栈撑爆。更稳妥的做法是改用迭代写法或者用BFS逆序处理。我现在的习惯是n小于5000用递归大于5000用迭代。这样既保证代码简洁又不会爆栈。7.2 忘记初始化多组数据时的经典错误有些题是多组测试数据每次都要重新初始化dp数组和邻接表。我有一次忘记清空邻接表导致上一组的数据混进来WA了好几发。后来养成了习惯每组数据开始前把所有全局数组重新赋值。Python里可以用[0]*(n1)重新创建C里用fill或者memset。7.3 循环顺序写反背包问题的老毛病树上背包的合并循环必须倒序和01背包一样。我有一次写成正序答案偏大debug了半小时才发现。后来我总结了一个口诀“背包合并倒序保平安”。只要是背包类的合并先检查循环顺序。7.4 根节点找错有向边和无向边的区别如果题目给的是有向边从父到子你需要自己找根入度为0的点。如果给的是无向边你需要用parent参数避免走回头路。我有一次把有向边当无向边处理结果dfs死循环。后来每次读题都先确认边的方向。8. 从刷题到实战树形DP在真实场景中的影子树形DP不只是竞赛题它在实际工程中也有应用。比如组织架构中的权限分配公司组织架构是一棵树每个部门有预算选了某个部门就必须选它的上级部门总预算有限求最大收益。这就是树上背包。文件系统的空间统计文件夹是一棵树每个文件夹有大小求删除某些文件夹后释放的最大空间同时满足依赖关系。网络路由的最优路径网络拓扑是一棵树求从根到所有叶子的最优路径或者求任意两点间的最长路径。这些场景的共同点是问题天然具有树形结构且子问题可以独立求解后再合并。一旦你识别出这个结构树形DP就是最自然的解法。我个人的体会是树形DP的难点不在代码而在状态定义和转移推导。代码写熟了之后大部分题都是模板化的。真正需要思考的是这道题的状态该怎么定父节点需要知道子树的什么信息合并的时候有没有顺序要求把这三个问题想清楚代码就是水到渠成的事。最后分享一个我练习树形DP的方法每做一道题先不写代码只在纸上画出树的结构标出每个节点的状态手动模拟一遍转移过程。这个过程比直接写代码慢但能帮你真正理解状态之间的关系。我坚持了这个方法一个月树形DP的正确率从50%提到了90%以上。如果你也在学树形DP不妨试试。