刷题刷到树形DP这一块很多人会有个特别明显的体感每一种转移方程单独拎出来看都不难可一旦要在赛场上现推状态、现写 dfs手就开始抖。我最早接触树形DP是做「没有上司的舞会」那道经典题看完题解觉得自己懂了合上题解重写子树合并的顺序、初值、循环边界全错了一遍最后交上去六发才过。这个算法真正的门槛不在懂不懂而在能不能一次写对。下面这份总结是我这几年刷题、打比赛、帮人看代码陆陆续续攒下来的笔记从状态设计的方法论讲到树上背包、换根DP、长链剖分这些进阶形态也包含我自己踩过的坑和几套可以直接抄走的模板。它适合已经会写基础线性DP、能用DFS遍历树但一碰到树形DP就卡壳的读者如果你刚学完数据结构建议先把邻接表和递归遍历写熟再往下看会顺畅很多。全文代码以C为主思路部分是语言无关的。1. 树形DP到底难在哪它和线性DP不是一个套路线性DP的世界里状态沿着一个维度平推f[i]只依赖f[i-1]、f[i-2]这类前面已经算好的位置顺序天然确定。树形DP把这张一维的表换成了树麻烦立刻从三个方向冒出来依赖关系不再是线性的、状态的合并对象有任意多个、递归的写法容易把答案覆盖掉。理解这三点基本就理解了树形DP的全部痛点。1.1 树的结构给DP带来的三个麻烦第一个麻烦是依赖方向不确定。在一棵以1为根的树里节点u的答案通常要等它所有儿子v的答案算完才能合并也就是说计算顺序是儿子先于父亲。但我们在写代码时又是从根往下递归的这就形成了递归方向向下、计算方向向上的反差初学的时候非常容易在递归函数里随手就把f[u]更新了结果用的是还没算完的儿子信息。第二个麻烦是合并对象数量不定。线性DP的转移项数固定树上一个节点的儿子可能是0个也可能是几十个。这意味着你不能写死转移式必须在循环里逐个儿子做增量合并而增量这个词是关键每处理完一个儿子f[u]就应该变成前若干个儿子合并后的结果而不是重新从零算。第三个麻烦是状态维度容易失控。树形DP经常要在状态里挂一些附加信息比如子树内选了j个点、距离u最近的被选中点在d层、子树内是否还剩未匹配的点。维度一多空间就炸转移的复杂度也跟着涨。我见过不少人的代码思路完全正确但状态开成f[100005][100005]直接MLE问题不出在算法上出在维度设计上。1.2 树形DP的通用骨架后序dfs加子树信息合并抛开具体的题目绝大多数树形DP都长成同一个样子我把这个骨架写出来你可以直接把它当成模板记void dfs(int u, int fa) { // 第一步初始化 u 自身的基础状态叶子节点的答案往往就是在这里定下的 init(u); for (int v : g[u]) { // 第二步逐个儿子处理 if (v fa) continue; // 无向图建树必须判父节点否则无限递归 dfs(v, u); // 先递归把儿子的答案算完整 merge(u, v); // 第三步把儿子的信息合并进 u } // 第四步在这里统计与 u 相关的全局答案比如经过 u 的路径 }这个骨架里有两个位置特别关键。一个是merge必须在dfs(v, u)之后调用也就是所谓的后序合并另一个是全局答案的统计位置有的题需要放在merge循环内部例如树的直径需要用到当前最长链和新来的链拼起来有的题需要放在循环外面例如子树大小统计。这两个位置放错了答案就是错的而且错得很隐蔽小数据可能还能过。1.3 什么时候该想到树形DP判断信号其实很明确。题干给出的图是一棵树或者可以简化成树要求你在满足某种约束的前提下最大化或最小化某个值并且这个约束具有子树内部局部性——也就是一个节点的决策只影响它所在的那棵子树或者只通过父节点影响外部。典型的场景包括树上选点不能选相邻的、树上分配预算给若干子任务、树上路径的最值统计、树上覆盖类问题。反过来说如果题目要求的是路径上的问题而且询问数量巨大那更可能是树链剖分或树上差分如果是子树整体的加减查询可能是DFS序加树状数组。树形DP擅长的是从下往上做决策把这句判断句记牢选算法的命中率会高很多。2. 状态设计树形DP最难的一步怎么落地写树形DP最耗时间的从来不是代码而是盯着题面想状态。我的经验是状态设计有一套固定的自问清单可以走这个节点的决策有几个选项子树内部需要向父节点汇报什么信息父节点拿到这些信息后够不够做出决策这三问走完状态基本就出来了。2.1 从选或不选出发的状态建模树形DP里最经典的状态形态是f[u][0/1]表示u 不选/选两种情况下子树的最优解。它的好处在于把相邻不能同时选这类约束表达得非常干净如果u选了儿子必须不选如果u没选儿子选不选都行取较大值。这种二值状态的转移f[u][1] f[v][0]; f[u][0] max(f[v][0], f[v][1]);只有两行但背后的思路可以推广到很多场景。比如每个点有代价选中的点要覆盖相邻边、每个点可以染两种颜色且相邻不同色、每个点有无激活两种状态且激活会向父节点传递信号。遇到新题时先试试用0/1两种状态能不能描述如果能问题瞬间降一档难度。需要注意的是f[u][0]的初值通常取0不选没有收益而f[u][1]的初值要取该点自身的权值。这一点看起来是废话但我改别人的代码时至少有三分之一的问题出在给f[u][0]也加了权值或者忘了给f[u][1]加。2.2 状态维度怎么加附加信息的挂载技巧当0/1不够用时就要往状态里加维度。加维度的原则是只挂父节点真正需要的信息其余信息在子树内部消化掉。举个例子如果题目要求选中的点中任意两个的距离不超过 k那么父节点需要知道的是子树内离 u 最近的选中点距离是多少于是状态变成f[u][d]d 表示距离。这个 d 的取值范围就是 0 到 k超过 k 的状态直接判为非法不需要压进数组。再比如子树内选了 j 个点这种背包型约束状态是f[u][j]。这时候数组大小要开成f[n][m1]m 是容量上限。如果 m 也很大比如1e5那就得考虑是不是能用贪心或者单调队列优化掉这一维而不是硬开内存。还有一个实用技巧把不可能达到的状态设成 -INF 或者 INF用极值来屏蔽非法转移。比如要求必须选恰好 k 个点那f[u][j]在j sz[u]时全部设成 -INF转移时自然会跳过。这个技巧比写一堆 if 判断干净得多。2.3 初始化与边界叶子节点是转移的起点树形DP的初始化只有两类一类是所有节点通用的基础状态一类是叶子节点的特殊处理。绝大多数情况下叶子节点的处理不需要单独写 if只要在dfs开头把基础状态设好然后 for 循环一次都不执行叶子节点自然就合并完了。真正要小心的是多组数据和全局变量复用。树形DP的代码往往用全局数组如果题目是多测忘了memset或者忘了清空邻接表头指针第二组数据就会出错。我一般会写一个clear()函数把head、cnt、f、sz全部重置在每组数据开始前调用一次。这看起来是笨办法但它比事后调试省太多时间。另外提醒一点根节点的答案需要单独取。因为dfs(1, 0)结束后f[1][0]和f[1][1]分别是1不选和1选两种情况的最优值最终答案是两者的较大值或者题目要求的某一项。很多人在dfs里顺手更新了一个全局ans但那个ans只统计了非根节点的情况根节点被漏掉答案就会偏小——这是树形DP里出现频率最高的错误之一。3. 三个必刷入门模型直径、独立集、重心把这三个模型吃透树形DP的基础功就算立住了。它们的共同点是状态简单、代码短但每一个都包含了树形DP的一个核心技巧直径考两条链拼接独立集考选或不选的约束传递重心考子树信息的统计与比较。3.1 树的直径两次DFS还是树形DP树的直径是树上最长路径的长度。传统做法是两次DFS第一次从任意点出发找到最远的点 a第二次从 a 出发找到最远的点 ba 到 b 的距离就是直径。这个做法正确而且代码短但它有个硬伤——只能处理边权非负的情况。如果边权是负数最远点法就失效了因为最远和最长路径在负权下不等价。树形DP的做法更通用也更值得掌握。定义dp[u]表示从 u 出发往子树方向走能得到的最大路径长度那么在遍历 u 的每个儿子 v 时有两条候选链一条是之前已经处理过的儿子提供的最长链dp[u]另一条是当前儿子提供的最长链dp[v] w(u,v)两者拼起来就是一条经过 u 的路径#include bits/stdc.h using namespace std; const int N 100005; struct Edge { int to, w, nxt; } e[N 1]; int head[N], cnt 0; int dp[N], ans 0; void add(int u, int v, int w) { e[cnt] {v, w, head[u]}; head[u] cnt; } void dfs(int u, int fa) { dp[u] 0; for (int i head[u]; i; i e[i].nxt) { int v e[i].to, w e[i].w; if (v fa) 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]已经被当前儿子污染拼出来的路径就会重复走同一条边。这就是我前面说的全局答案统计位置的典型例子。3.2 最大权独立集没有上司的舞会这道题的题意是n 个人构成一棵上下级树每个人有一个快乐值一个人如果参加舞会他的直接上司不能参加问最大快乐值总和。状态定义f[u][0]表示 u 不参加时子树的最大值f[u][1]表示 u 参加时的最大值。int f[N][2]; void dfs(int u, int fa) { f[u][0] 0; f[u][1] a[u]; for (int v : g[u]) { if (v fa) continue; dfs(v, u); f[u][0] max(f[v][0], f[v][1]); // u 不参加儿子随意 f[u][1] f[v][0]; // u 参加儿子必须不参加 } } // 最终答案max(f[root][0], f[root][1])这两行转移值得反复咀嚼。它体现的是一个通用模式当父节点的决策会限制子节点的选择时把限制关系直接写进转移式里而不是写完再看合不合法。这种在转移中约束的思路可以一路推广到树上染色、树上覆盖、树上匹配等一大类问题。3.3 重心与子树统计一遍dfs能拿到多少信息树的重心定义为删掉该点后剩下的所有连通块中最大块的大小最小。求重心的过程只用一遍 dfs但里面藏着两个技巧。int sz[N], heavy[N]; void dfs(int u, int fa) { sz[u] 1; heavy[u] 0; for (int v : g[u]) { if (v fa) continue; dfs(v, u); sz[u] sz[v]; heavy[u] max(heavy[u], sz[v]); } heavy[u] max(heavy[u], n - sz[u]); // 父方向的那一块 if (heavy[u] heavy[ans]) ans u; }第一个技巧是n - sz[u]这一项。删掉 u 之后除了它各个儿子的子树还有u 的父节点那一侧这一大块它的大小正好是n - sz[u]。忘了这一项求出来的就是最大子树最小而不是重心这是非常隐蔽的错误。第二个技巧是在 dfs 过程中顺手统计sz。子树大小这个信息几乎是树形DP的必备辅助量很多题目的状态数组大小、循环上界都要靠它来卡。我的习惯是只要题目涉及树形DP就先写一个求sz的 dfs 打底后面再往上加状态。4. 树上背包树形DP里错得最多的一类树上背包是树形DP和背包问题的交叉形态典型场景是给每个节点分配一定的资源节点内部有代价和收益问总量限制下的最大收益。它的状态本身不复杂但循环的写法几乎每个人都会错一次而且错法高度雷同。4.1 为什么合并顺序和循环方向都是坑先看标准写法void dfs(int u, int fa) { sz[u] 1; f[u][0] 0; f[u][1] a[u]; // 假设选 u 需要占用 1 的容量 for (int v : g[u]) { if (v fa) continue; dfs(v, u); for (int j min(sz[u], K); j 1; --j) // 已合并部分的容量倒序 for (int k 1; k min(sz[v], K - j); k) // 当前儿子贡献的容量 f[u][j k] max(f[u][j k], f[u][j] f[v][k]); sz[u] sz[v]; } }这里有三处不能动的地方第一外层循环 j 必须倒序。因为f[u][jk]依赖的是f[u][j]在同一轮儿子合并中的旧值正序会把同一个儿子重复计算变成选多次。这一点和01背包的倒序思路完全一致但很多人写树形背包时就忘了。第二j 的下界是1不是0。如果容量从0开始就会出现u 一次都没被选却往里塞儿子的情况答案会偏大。当然如果题目允许 u 不占容量下界改成0也合理关键要想清楚 u 自身是否占位。第三k 的上界要用K - j卡住。不卡的话数组会越界而且会算出容量超限的非法状态。这个细节在容量小的时候不容易暴露一旦 K 稍大就越界表现为莫名的RE或乱码答案。4.2 复杂度到底是不是O(n^3)很多人一听树上背包就觉得是 O(n·K²) 甚至 O(n³)于是不敢用。实际上如果你在合并时用sz[u]和sz[v]做上界限制总的合并次数是 O(n²) 级别的。直觉上的解释是每一对节点 (x, y) 只会在它们最近公共祖先处被合并一次所以总合并对数是 O(n²)。如果把容量限制 K 也算进去复杂度是 O(n·K) 到 O(n·K²) 之间取决于具体实现。这个分析很重要因为它决定了你能不能放心地把树上背包用在 n 2000 甚至 n 5000 的数据上。我的建议是只要写了sz上界优化n 到5000、K 到100基本都可以放心用。4.3 可复现的模板与上下界优化除了min(sz[u], K)这种基础优化还有一个常被提到的上下界优化外层 j 的下界可以设成已合并部分的最小可能容量而不是从1开始。比如如果每个被选中的节点至少占1的容量且当前已合并了pre个节点那么 j 至少要等于pre如果要求 u 必选或者更小的值。这个优化的收益在稠密约束下比较明显但代价是代码可读性下降边界条件更容易写错。我的实际建议是先写最朴素的j从大到小、k从1到min(sz[v], K-j)的版本测出复杂度不够再优化。优化本身只带来常数级别的改善但如果因为优化写错了边界损失的是一个小时的调试时间不划算。另外提一句如果状态的容量维是选了恰好 j 个点而不是容量不超过 j初始化时要把f[u][j]在j ! 1时全设成 -INF只有f[u][1] a[u]是合法的。这个细节决定了恰好和至多两种题型的答案是否一致混淆的话会出现输出多了一点点的诡异现象。5. 换根DP把以1为根升级成全局答案前面所有模型都有一个隐含前提答案与根的选择无关或者题目已经指定了根。但有一类题长这样——对每个点求出以它为根时的某个值。暴力对每个点跑一次 dfs 是 O(n²)n 大一点就超时。换根DP把这个过程压到 O(n)核心思路是先以1为根算一遍再通过父子关系递推把根从父亲搬到儿子。5.1 二次扫描的推导思路换根DP的标准流程分两步。第一步通常叫dfs1以1为根算出每个节点子树内的信息比如子树大小sz[u]、子树内所有点到 u 的距离和down[u]。第二步通常叫dfs2从根出发用父亲的全局答案推出儿子的全局答案。以求所有点到指定点的距离和为例定义f[u]表示所有点到 u 的距离之和。那么f[1]就是down[1]可以直接从第一步拿到。接下来考虑怎么从f[u]推f[v]其中 v 是 u 的儿子。5.2 换根公式的推法减法而不是重新算当根从 u 移到 v 时整个点集被分成两块v 的子树大小sz[v]和其余部分大小n - sz[v]。对于 v 子树内的点它们到 v 的距离比到 u 的距离各少了1总贡献减少sz[v]对于其余的点它们到 v 的距离比到 u 的距离各多了1总贡献增加n - sz[v]。于是f[v] f[u] - sz[v] (n - sz[v]) f[u] n - 2 * sz[v]这一步是整个换根DP的灵魂建议自己动手在纸上画三个点的链推一遍比看十遍公式记得牢。实现出来是这样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]; // 子树内每个点到 u 的距离 } } void dfs2(int u, int fa) { for (int v : g[u]) { if (v fa) continue; f[v] f[u] n - 2 * sz[v]; // 换根公式 ans min(ans, f[v]); dfs2(v, u); } } // 主函数里dfs1(1, 0); f[1] down[1]; dfs2(1, 0);5.3 换根DP常见的重复计算陷阱换根DP最容易出问题的不是公式本身而是**哪些信息在换根时会变**。上面这个例子里sz[v]是不变的因为子树划分不随根变化在有根 meaning 下以1为根时的子树关系是固定的。但如果题目要求的是以 u 为根时的最大深度那换根时子树的最大深度和次大深度都会变必须预存最长链和次长链并且判断儿子贡献的是不是最长的那条链如果是就要改用次长链。这个细节是换根DP进阶题的高频考点漏了就会出现答案偶发偏小。另一个陷阱是根节点的f值来源。f[1] down[1]这个赋值不能少也不能放在 dfs2 里面。我见过有人把f[1]初始化成0结果整棵树的结果全部偏移了一个固定量小数据下完全看不出来只有大数据的答案会整体偏小。6. 树形DP的扩展形态与组合技单纯考树形DP的题现在越来越少了主流考法是把它和别的技巧缝在一起。这一章列几种我实际遇到过的组合形态以及每种的接口在哪里。6.1 与二分答案结合树上最小化最大值经典形态是在树上放置若干个设施使得最远未被覆盖的点距离尽可能小。做法是二分答案mid然后在树上做贪心式的树形DPf[u]表示 u 子树内距离 u 最近的设施距离同时维护子树内最远的未被覆盖点的距离。如果某个未被覆盖点的距离加上当前点已经无法被覆盖就必须在这里新建一个设施。这种题的接口在于二分的单调性要成立设施数量随半径增大而单调不增。写之前先确认这一点否则二分出来的结果没意义。另外贪心的正确性需要严格论证通常是能拖到父节点再放就拖因为父节点覆盖范围更大这个直觉在多数题里成立。6.2 与基环树结合断环成树基环树就是树加一条边n 个点 n 条边。处理方法很固定找到环把环上的一条边断开然后分两种情况讨论——这条边连接的两个点必须不同时选和必须同时选或者干脆强制一个选一个不选。两种情况的答案取最优就回到了普通的树形DP。找环用拓扑排序最稳把所有度为1的点入队不断删点最后剩下的就是环上的点。这个方法比一遍 dfs 找环的代码更短、更不容易错。6.3 长链剖分把深度相关的合并压到O(n)当树形DP的状态与深度相关比如f[u][d]表示 u 子树内深度为 d 的信息时朴素的合并是 O(n²)。长链剖分通过把最长儿子的数组直接继承给父亲的方式把总的合并次数降到 O(n)。具体的做法是预处理出每个节点的长儿子子树深度最大的儿子然后在 dfs 时让父亲直接复用自己的长儿子的数组空间短儿子暴力合并。关键在于数组空间的分配要预先按长链连续分配父亲和长儿子共用同一块内存。这个技巧代码量不小建议先背模板再理解否则很容易在指针偏移上绕晕。6.4 与状压、贪心、剪枝的搭配如果子树内部的决策量很小比如不超过20种状态可以把子树的决策压成一个二进制数存进状态这是树形DP加状压的典型用法。如果题目有明显的贪心性质比如每次选最优的儿子一定不亏可以先用树形DP验证小数据再改成贪心或加上剪枝。剪枝本身不是算法但在树形DP的搜索版本里一个当前最优不可能被超越就返回的判断能让常数大幅下降。7. 调试实录报错、超时、答案偏小的排查清单树形DP的错误几乎都能归到几类里。我把这些年遇到的和帮别人看代码时发现的整理成一张表出问题时按顺序排一遍命中率很高。7.1 常见错误速查表现象最可能的原因排查方法答案偏小根节点答案没统计进去检查最终输出是不是只取了非根节点的ans答案偏大背包内层循环没倒序同一儿子被重复选把 j 改成从大到小数组越界 / RE合并时上界没卡min(sz[v], K - j)打印每次循环的 j、k 范围无限递归 / 栈溢出无向图建树没判父节点检查if (v fa) continue;第二组数据答案错多测没清空全局数组和邻接表写clear()函数统一重置局部答案对、全局错ans更新位置在dp更新之后交换两行顺序深度大的数据挂掉递归层数超过默认栈改迭代或调大栈空间这张表里的答案偏小和答案偏大我单独解释过但值得再强调一次树形DP的答案偏差往往是有规律的偏小通常是少算了一类情况偏大通常是同一份贡献算了两次。看到 WA 时先看偏差方向再对着表找比盲改快十倍。7.2 对拍脚本与暴力验证树形DP的调试强烈建议用对拍。因为它不像线性DP那样可以手算几组树的结构一复杂手算就容易出错。我的对拍流程是写一个暴力版本枚举所有子集或者对所有根都跑一遍再写一个专门的随机数据生成器然后用脚本循环比对。#!/bin/bash g -O2 -o std solution.cpp g -O2 -o brute brute.cpp g -O2 -o gen gen.cpp for ((i 1; i 1000; i)); do ./gen in.txt ./std in.txt out1.txt ./brute in.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo WA on test $i cat in.txt break fi done echo done生成器里有个小技巧随机树不要用rand() % n 1当父亲要保证生成的树有一定的深度。全随机的父亲容易生成菊花图根连着几乎所有点而很多树形DP的 bug 只在深度大的链状树上才暴露。我的做法是混合生成一部分数据用i的父亲取rand() % i 1偏链状一部分用rand() % (n/10) 1偏深两种混着测。7.3 卡常、爆栈与内存处理递归写深的树n 到 1e5 以上且是一条链时C 默认的栈空间可能不够。在本地 Windows 环境下可以加一句#pragma comment(linker, /STACK:1073741824)在评测平台上更稳的做法是改成手写栈的迭代版本。做法是用一个栈模拟后序遍历第一遍把节点按 dfs 序压入数组然后倒着遍历这个数组做合并。这个改写对大多数树形DP都适用只需要把merge的逻辑从递归里挪到逆序遍历的循环里。内存方面如果状态数组是二维的f[N][K]注意 N 和 K 的乘积不要超过内存限制。n 1e5、K 100 时int数组就是 40MB加上其他数组很容易超。这种情况要么用short存前提是值域允许要么考虑是否存在滚动数组的可能——树形DP本身不太适合滚动因为子树的答案需要完整保留但如果题目只有深度相关的一维长链剖分可以省下大量空间。最后再分享一个我个人的习惯写树形DP前先手写三组小数据一组链、一组菊花、一组完全二叉树把预期答案算出来。代码写完先跑这三组全过了再交。这个习惯帮我省下的罚时比任何优化都多。