1. 树形DP到底解决什么问题第一次接触树形DP是在做一道没有上司的舞会的题目时当时我盯着题面看了半小时也没想明白为什么一个看起来像贪心或者搜索的题最后要用动态规划去做。后来刷的题多了才慢慢体会到树形DP其实是动态规划里一个非常特殊的分支它的特殊性不在于状态转移方程有多难写而在于整个问题的结构是建立在一棵树上的。树形DP的核心思路可以用一句话概括在树上做动态规划状态的转移沿着树的父子关系进行。听起来简单但真正写起来很多人会卡在三个地方——状态怎么定义、转移怎么写、边界怎么处理。这篇文章我打算把这三个问题拆开讲透从最基础的树上背包讲到换根DP把我踩过的坑和总结出来的套路都写清楚。适合读这篇的人应该已经掌握基本的动态规划思想知道什么是状态、什么是转移也写过一些线性DP的题。如果你还在纠结斐波那契的递推怎么写那建议先把基础的DP练熟再来看树形DP。反之如果你已经能熟练写背包、区间DP那这篇内容会让你对在树上做DP这件事有一个系统性的理解。树形DP的典型应用场景其实非常集中常见的有树上选择问题比如选或不选某个节点节点之间有依赖关系父节点选了子节点才能选树上路径统计统计满足条件的路径数量或最大权值树上覆盖问题用最少的点覆盖整棵树或者在树上放置某些设施树上依赖背包每个节点是一个物品组选子节点必须先选父节点这些问题单独看都不太难但它们的共性在于父子的依赖关系这个结构。树形DP正是利用这个结构把整棵树的答案拆解成子树答案的组合。1.1 为什么树形DP要用递归而不是递推很多人一开始会疑惑为什么树形DP几乎清一色地用递归实现而不是像线性DP那样用循环递推。这个问题我当年也困惑过后来想明白了线性DP之所以能递推是因为状态之间的依赖关系是一个有向无环图且这个图可以被拓扑排序成一个线性序列。比如背包问题中容量从小到大递推f[i] 只依赖于 f[i-1]顺序天然确定。但树的结构不一样。一棵树的节点之间没有天然的全序关系一个节点的父节点和它的兄弟们之间谁先算取决于你从哪个角度遍历。唯一保证子节点先于父节点计算的方式就是用后序遍历也就是递归回溯。递归到叶子节点时叶子没有子节点状态可以直接初始化回溯到父节点时所有子节点的状态都已经算好直接拿来合并即可。所以树形DP的递归框架基本是固定的void dfs(int u, int fa) { // 1. 初始化 u 的状态 for (int v : g[u]) { if (v fa) continue; // 防止走回父节点 dfs(v, u); // 先递归处理子树 // 2. 用 v 的状态更新 u 的状态 } }这个框架看起来简单但要注意fa参数的传递。树的存储通常是邻接表边是无向的如果不传父节点递归会沿着边跑回父节点直接死循环。这是新手最容易踩的第一个坑。注意当树退化成链时递归深度可能达到节点数。如果你的树有十万甚至百万个节点递归栈可能会爆。这种时候要么手动开栈Windows下用#pragma comment(linker, /STACK:...)Linux下用ulimit -s要么改成迭代版的显式栈后序遍历。这一点做大数据量的题时必须提前考虑。1.2 树形DP和普通DP的本质区别有人可能会问树形DP不就是在树上做DP吗和普通DP能有什么区别。我个人的理解是区别在于状态转移的维度。线性DP的状态通常是一维或两维转移是状态之间的加减乘除而树形DP的状态往往是以 u 为根的子树这个整体转移是子树之间的合并。举个例子没有上司的舞会里状态定义是f[u][0/1]表示以 u 为根的子树中u 选或不选时的最大快乐值。这里的子树两个字非常关键它意味着这个状态包含的是一整棵子树的信息而不是单个节点的信息。这个视角的转变是理解树形DP的关键。再比如树上背包问题状态是f[u][j]表示以 u 为根的子树中选了 j 个物品或花费了 j 的容量时的最优值。这里的 j 就是子树合并时产生的额外维度也是树形DP比较复杂的地方——合并两个子树的时候本质上是在做一次卷积。1.3 从一道入门题看树形DP的完整流程拿没有上司的舞会这道经典题走一遍完整流程能帮大家把上面的理论落地。题目大意是一棵树上的每个节点有一个快乐值选了一个节点就不能选它相邻的节点求最大快乐值总和。第一步状态定义。因为是树形结构状态一定要挂在节点上而且要考虑选不选当前节点这个决策因为它直接影响子节点能不能选。所以定义f[u][0]以 u 为根的子树中不选 u 时的最大快乐值f[u][1]以 u 为根的子树中选 u 时的最大快乐值第二步状态转移。如果 u 不选那么子节点 v 选不选都行取最大值如果 u 选那么子节点 v 一定不能选。f[u][0] max(f[v][0], f[v][1]); f[u][1] f[v][0];第三步边界初始化。递归到叶子节点时f[u][0] 0f[u][1] a[u]a[u] 是节点 u 的快乐值。第四步答案。根节点的两个状态取最大值max(f[root][0], f[root][1])。这四步就是树形DP的标准流程。后面所有的树形DP题无论多复杂本质都是这四步的变体。2. 树形DP的几种经典模型与套路掌握了基本框架之后真正决定你能走多远的是见过多少模型。树形DP的题目变形非常多但归纳起来其实就那么几类。我把它们整理成表格方便对照。模型名称状态设计特点典型题目树上相邻选择f[u][0/1]表示选不选 u没有上司的舞会树上背包f[u][j]加上容量维度有线电视网、选课树上路径统计f[u]表示以 u 为端点的路径树的直径、树的最长路径树上覆盖f[u][0/1/2]多状态战略游戏、监控站换根DP两次DFS一次求子树一次换根树的中心、子树大小树上依赖背包背包依赖树金明的预算方案树版下面我把这几个模型逐一拆开配合具体题面和代码。2.1 树上背包最容易写出 O(n^3) 的一类题树上背包是树形DP里出现频率最高的模型之一。它的核心思想是把子树看成一个物品组在父节点处做分组背包。典型题面是给一棵树每个节点有一个价值和一个重量选一个子节点必须先选它的父节点或者说选了一个节点就能选它的子树问容量为 m 时能获得的最大价值。这种题的转移方程看起来是这样的// f[u][j] 表示以 u 为根的子树中选 j 个节点的最大价值 for (int v : g[u]) { dfs(v, u); for (int j siz[u]; j 1; j--) { for (int k 1; k min(j, siz[v]); k) { f[u][j] max(f[u][j], f[u][j - k] f[v][k]); } } siz[u] siz[v]; }这段代码有两个关键点。第一内层的 j 必须倒序枚举因为我们在用 f[u][j-k] 更新 f[u][j]正序会出现同一子树被选多次的情况本质上和01背包倒序是一个道理。第二k 的上界是min(j, siz[v])如果不加这个限制会退化成 O(n^3) 甚至更高。加上之后利用每棵子树的大小作为上界总复杂度可以证明是 O(n^2) 的。提示虽然很多资料说树上背包是 O(n^2)但这个结论成立的前提是每个子树大小作为枚举上界。如果你偷懒直接枚举到 m复杂度会变差。这个细节在数据量大的题目里是决定能不能过掉的关键。我当年在写有线电视网这题时就是因为没有加siz优化卡了好几个测试点。后来看到别人的代码才发现这个技巧。siz[u] 的维护要放在更新完之后这也很关键如果放错了位置siz 会算错。2.2 树上路径统计直径问题及其变种树上路径统计的经典代表是求树的直径——树上最长的简单路径长度。这个问题的解法有两种两次DFS/BFS或者树形DP。两次BFS的方法只能处理边权非负的情况而树形DP可以处理负权边这是它的优势。树形DP求直径的思路是对于每个节点 u维护从 u 往下走的最长路径和次长路径这两条路径来自不同的子树合并起来就是以 u 为转折点的最长路径。int dfs(int u, int fa) { int mx1 0, mx2 0; // 最长和次长 for (int v : g[u]) { if (v fa) continue; int d dfs(v, u) w[u][v]; // 子树v给出的路径长度 if (d mx1) { mx2 mx1; mx1 d; } else if (d mx2) { mx2 d; } ans max(ans, mx1 mx2); // 更新全局答案 } return mx1; }这段代码的精髓在于 mx1 和 mx2 的维护。因为是不同的子树所以 mx1 和 mx2 一定来自两条不同的分支把它们加起来就是以 u 为最高点的最长路径。全局答案 ans 在所有节点处取最大值。这里有个容易犯的错误更新 ans 的位置。有人习惯在循环外面更新一次但这样会漏掉从 u 只往下走一条路的情况虽然对于直径来说单条路径通常不会是最长的但如果是求经过 u 的最长路径这种变体就必须在循环内更新。我现在习惯在每次更新 mx1/mx2 之后立刻更新 ans这样最保险。2.3 树上覆盖多状态DP的经典应用树上覆盖问题的典型代表是战略游戏在树上的某些节点放士兵每个士兵能覆盖它相邻的边求覆盖所有边所需的最少士兵数。这题的难点在于状态设计。因为一个节点放不放士兵会影响到它和父节点的边、它和子节点的边。所以状态至少要分三种f[u][0]u 不放士兵且 u 与父节点的边已经被父节点覆盖f[u][1]u 放士兵f[u][2]u 不放士兵且 u 与父节点的边需要被子节点覆盖转移方程看起来是这样f[u][0] sum(min(f[v][1], f[v][2])) // 子节点v必须覆盖它和u的边 f[u][1] 1 sum(min(f[v][0], f[v][1], f[v][2])) // u放士兵子节点随意 f[u][2] min over v (f[v][1] sum_{v ! v} min(f[v][1], f[v][2])) // 找一个子节点放士兵第三个转移是这题的精髓需要额外扫一遍找放士兵代价最小的子节点。这个转移的写法有个小技巧先假设所有子节点都不放士兵取 min(f[v][1], f[v][2])然后找一个差值最小的子节点改成放士兵。实操心得这种先全选一个方案再调整一个特殊元素的技巧在多状态树形DP里非常常见。我一般会把差值存到一个变量里最后加到答案上比在循环里反复判断要清晰。2.4 换根DP从祖先视角到全局视角换根DP是我觉得最聪明的一类树形DP。它的思路是先用一次DFS求出以某个节点通常是1号为根时子树的信息然后再用一次DFS把根换到每个节点上求出每个节点作为整棵树的根时的答案。典型题目是求树的重心或求每个节点到其他所有节点的距离和。后者的状态转移非常经典设siz[u]为以 u 为根的子树大小f[u]为以 u 为根时所有节点到 u 的距离和。第一次DFS求出 siz 和 f[1]。第二次DFS时如果从 u 换根到 vv 是 u 的子节点则有f[v] f[u] - siz[v] (n - siz[v])这个公式的含义是原来有 siz[v] 个节点到 v 的距离比到 u 近1换根后有 (n - siz[v]) 个节点到 v 的距离比到 u 远1。所以 f[v] f[u] - siz[v] (n - siz[v])。理解这个公式是掌握换根DP的关键。它本质上是在做增量的传播——不是重新计算而是利用已知答案推导新答案。换根DP还有个常见的坑当根有多个子节点时第一次DFS求的 f[1] 需要先算出所有子树的信息再整合。这个顺序不能乱。3. 从零实现一个完整的树形DP题目光看理论没用来一道完整的题目从头写到尾。选课这道题是树形DP里我认为最经典的一道它的结构清晰又能覆盖树上背包的核心思想。3.1 题目分析与状态设计题目大意有 n 门课每门课有学分每门课有先修课或没有先修课选一门课必须先选它的先修课。求选 m 门课能获得的最大学分。这道题的结构天然就是一棵树先修课是父节点被先修的是子节点。没有先修课的课我们人为加一个虚拟根节点0指向所有没有先修课的课。这样整棵树就完整了。状态定义f[u][j]表示在以 u 为根的子树中选了 j 门课并且选了 u的最大学分。为什么强调并且选了 u因为题目规定选子节点必须先选父节点所以如果选了 u 的子树里的课u 必然被选。这个约束可以让状态转移简化。3.2 转移方程的详细推导对于节点 u初始化f[u][1] score[u]选 u 这一门课。然后对每个子节点 vfor (int j m 1; j 1; j--) { // 倒序遍历容量 for (int k 1; k j; k) { // 枚举分配给子树的课数 f[u][j] max(f[u][j], f[u][j - k] f[v][k]); } }注意这里的循环上界是m 1因为虚拟根节点0也要占一个位置。最终答案在f[0][m 1]选了0号节点和 m 门真实课程。这个推导过程中有个细节值得说为什么 k 要从1开始而不是从0开始因为 f[v][0] 表示选了0门课这在我们的状态定义下没有意义——既然子树的课一门都不选那这个子节点 v 就不应该在转移里出现。所以 k 从1开始保证每个被考虑的子节点至少选了一门课。3.3 代码实现与复杂度分析完整代码#include bits/stdc.h using namespace std; const int N 305; int n, m; int f[N][N], siz[N], score[N]; vectorint g[N]; void dfs(int u) { siz[u] 1; f[u][1] score[u]; // 选u for (int v : g[u]) { dfs(v); for (int j min(siz[u] siz[v], m 1); j 1; j--) { for (int k 1; k min(siz[v], j - 1); k) { f[u][j] max(f[u][j], f[u][j - k] f[v][k]); } } siz[u] siz[v]; } } int main() { cin n m; for (int i 1; i n; i) { int p; cin p score[i]; g[p].push_back(i); } dfs(0); cout f[0][m 1] endl; return 0; }复杂度方面由于限制了 k 和 j 的上界整体是 O(nm) 级别准确说是 O(nm n^2) 的混合视实现而定。这个复杂度对于 n300、m300 的题目完全够用。注意siz 数组的初始化必须在进入子树循环之前完成。我见过有人把它放在循环里面结果每次循环都重置siz 永远是错的。3.4 调试过程与验证方法写完之后怎么验证我一般用两个方法。第一个方法是手算小数据。比如 n3m2树结构是 1 是根2、3 是1的子节点学分分别是 5、3、4。手动枚举所有选法选1、25 3 8选1、35 4 9选1、2、3但只能选2门不合法所以答案是9。跑程序验证如果输出9就说明代码逻辑基本正确。第二个方法是对拍。写一个暴力枚举所有子集的程序n≤20时可行随机生成树和数据对比两个程序的输出。这个方法能发现绝大多数隐藏的bug尤其是边界情况。我写复杂树形DP时基本都会对拍一轮。4. 树形DP常见问题与排查技巧写了这么多树形DP我把遇到过的典型问题整理成速查表方便大家排查。问题现象可能原因解决办法程序死循环递归时没传父节点加fa参数if (v fa) continue答案偏小状态初始化遗漏检查叶子和根节点的初始化答案偏大转移时重复选择同一子树检查容量维度是否倒序枚举结果不确定siz 维护时机错误siz 更新要放在子树合并之后大数据超时未用 siz 优化枚举上界用min(j, siz[v])栈溢出崩溃树的深度过大手动开栈或改迭代结果差1根节点计数问题检查是否算了虚拟根节点逐条说下这几个问题。死循环问题是最常见的。树用无向边存储如果递归时不判断父节点就会在两个相邻节点之间来回跳。这个错误的典型表现是程序直接卡死或者爆栈。修法很简单加一个fa参数即可。但要注意的是如果树的结构不是标准的父指向子而是用了某些特殊的存储方式比如父指针数组那就不需要传 fa判断方式也不同。状态初始化遗漏这一类问题很隐蔽。因为程序能跑出结果只是结果不对往往要对比正确答案才能发现问题。我的经验是每次写完状态转移立刻回头检查所有状态的初始值是否被正确设置。特别是那些表示不可能状态的初值比如求最小值时通常初始化为 INF求最大值时初始化为 -INF。重复选择同一子树的问题是树上背包特有的。原因是内层循环没有倒序导致同一棵子树在更新 f[u][j] 时被多次使用。这和01背包倒序的本质是一样的只要记住用旧状态更新新状态时容量维度倒序这条规则就不会犯这个错。siz 维护时机这个坑我踩过不止一次。siz 数组的作用是记录子树大小作为枚举上界。但如果在合并子节点之前就更新 siz[u]那么这次合并时用到的上界就是错的。正确的做法是先完成本次合并再siz[u] siz[v]。另外要注意 siz[u] 的初始值是1u 自己不是0。复杂度优化这一块最有效的就是利用 siz 限制枚举上界。除此之外还有一个技巧是只保留有用的状态比如某些题目里状态值小于0的可以直接剪掉。不过这类技巧比较依赖具体题目通用性不强。实操心得我调试树形DP题时习惯先输出每个节点的 f 数组看看尤其关注叶子节点和根节点。叶子节点的值应该等于初始化值根节点的值应该等于最终答案。如果这两个地方不对问题一定出在转移或初始化上。还有一个比较隐蔽的问题是多组数据时的清空。有些题目会有多组测试数据每组的 n 不同。这时候 f 数组、g 邻接表、siz 数组都需要重新初始化。我通常会在dfs函数或者主函数开头统一清空避免残留数据导致错误。最后再分享一个我个人的小习惯写树形DP时我习惯把状态定义写在注释里尤其是带多个维度的状态比如f[u][0]表示什么f[u][1]表示什么。这是因为树形DP的状态含义经常容易搞混写着写着就忘了自己定义的是什么。有了注释对照调试时能省很多功夫。这个方法在写多状态树形DP比如三状态的树上覆盖时尤其有用。关于进阶方向树上问题其实还有不少值得深挖的点比如树链剖分配合树形DP、树上莫队、DSU on tree树上启发式合并。这些内容比基础的树形DP要难不少但核心思想仍然是一脉相承的——都是利用树的子树结构来降低问题的复杂度。等把基础的树形DP练熟了这些进阶内容会容易上手很多。