第一次被树形DP按住摩擦是很多年前做一道没有上司的舞会的题。当时我脑子里全是线性DP那套从左到右推的直觉结果题面给的是一棵树,我盯着那堆父子关系愣是不知道状态该往哪儿放。后来做多了才发现,树形DP根本不是另一种DP,它就是在一棵树上做后序遍历,把每个子树当成一个独立的小问题先解干净,再往上合并。想通这一点之后,树上背包、换根DP、树的直径这些看起来花里胡哨的东西,其实就是同一个骨架套不同的状态定义。这篇笔记我打算把这套骨架拆开讲透,从最基础的子树状态设计,到树上背包的复杂度优化,再到换根DP的推导,顺便把我踩过的几个经典坑一并说清楚。不管你是在准备算法竞赛,还是在啃数据结构与算法这门课,只要你会写递归、懂动态规划的基本套路,这篇文章应该能让你对树形DP有个完整的抓手。1. 树形DP的骨架递归序为什么就是天然的状态转移顺序1.1 线性DP和树形DP最根本的区别线性DP处理的是一段区间或者一个序列,状态之间存在天然的前后顺序,你从下标小的推到下标大的就行,那个方向是明确的。树形DP面对的是一个树结构,节点之间只有父子关系,没有全局的从前到后。这时候判定的标准变成了:一个节点的状态能不能只靠它自己的信息和它所有子树的信息推出来。关键在于树有一个性质:把任意一个节点拎出来,它的整棵树就被分成这个节点本身和它每个儿子的子树两大块,而这些子树之间是完全不重叠的。这意味着,只要我们把每个儿子子树的状态先算好,父节点的状态就可以通过合并这些子结果得到。这个先算子后算父的顺序,恰好就是后序遍历。我习惯把它理解成拆快递:每个子树是一个包裹,你得先把所有小包裹都拆开、清点完,才能把里面的东西汇总到更大的箱子里。你没法跳过小包裹直接算大箱子,因为没有全局的顺序,只有这种自底向上的依赖。1.2 后序遍历保证子问题先解完写树形DP的时候,递归函数的形态基本都是这样:进入函数先初始化当前节点的状态,然后遍历它的每个儿子,递归调用,等递归返回之后,把儿子的结果合并到当前节点上。整个过程中,当前节点的状态在被合并之前,只包含已经处理完的儿子的贡献。这一点非常重要,因为它直接决定了你在合并的时候能不能就地修改父节点的数组。比如你在处理儿子v的时候,父节点u的状态里混着v的结果,再和v的结果做运算,那就会重复计算,典型的自己吃自己。所以合并的正确姿势是:先把u已有的结果和v的结果算出来放到一个新数组里,或者用一个临时的旧值来参与计算,算完了再覆盖回去。后面讲树上背包的时候我会重点说这个,因为它是最容易写出错误答案的地方。还有个细节是根的选择。树是无根的,理论上选哪个点当根都行,因为子树划分只是相对的。但不同根会让某些问题的状态定义变得别扭,所以选根要看题目:求子树相关的东西,根随便选;求路径相关的,往往要每个点都当一次根来看,这就是后面要讲的换根DP。1.3 建图和递归边界的标准写法树形DP的第一步永远是建图。绝大多数题目给的是n-1条无向边,我一般用邻接表存,然后从根节点开始DFS。这里有个细节,因为树是无向的,你在遍历儿子的时候必须判断下一个点是不是我的父亲,否则会顺着来路往回走,直接栈溢出或者死循环。标准的写法是递归函数带一个父亲参数,遍历邻居时跳过父亲:void dfs(int u, int fa) { // 初始化 dp[u] for (int i head[u]; i ! -1; i edge[i].nxt) { int v edge[i].to; if (v fa) continue; // 跳过父亲,防止回头 dfs(v, u); // 先把子树处理完 // 合并 v 的贡献到 u } }这段模板几乎能套住八成的树形DP题。注意dfs(v, u)放在合并语句之前,这就是后序遍历的体现。如果你不小心把合并写在递归前面,那用到的还是v未初始化或者上一轮的状态,答案必然错。提示:如果题目给的节点编号从1开始,记得head数组和边数组都开够,通常2*(n-1)条边,别只开n。2. 状态怎么定从选不选到选几个树形DP真正难的不是递归,而是状态定义。同一棵树,状态设计得好,转移两行搞定;设计得差,写得你自己都看不懂。我把它分成三个层次来理解,基本能覆盖大多数题目。2.1 一维状态没有上司的舞会最经典的入门题。题意是每个节点有一个快乐值,父子不能同时被选,求能选出的最大快乐和。这题的状态设计的核心矛盾是这个点选还是不选,选和不选会直接限制儿子能不能选,所以必须把选/不选这个信息编码进状态。于是状态就是dp[u][0/1],第二维表示u是否参加:dp[u][0]:u不参加时,以u为根的子树能得到的最大值dp[u][1]:u参加时,子树能得到的最大值转移逻辑很顺:如果u不参加,儿子的选不选不受限制,取两者大的:dp[u][0] max(dp[v][0], dp[v][1])如果u参加,儿子一定不能参加:dp[u][1] dp[v][0]初始化就是dp[u][1] a[u],dp[u][0] 0。最后答案是max(dp[root][0], dp[root][1])。这题教会我一个通用套路:当节点自身的选择会影响子节点的合法状态时,把自身的选择做成一维。这个思路在后面的树形依赖背包、树上染色类问题里反复出现。2.2 二维状态树上背包的体积维度当问题从选不选升级到选几个,状态就要再加一维容量。最典型的是选课这类题目:每个节点有学分,选了儿子必须先选父亲,一共只能选m门,求最大学分。这时候状态是dp[u][j],表示以u为根的子树里,选了j个节点(包含u自己)能得到的最大价值。为什么带上包含u这个约定?因为题目要求选儿子必须先选父亲,所以只要子树里选了东西,u就一定被选了,把它定死在状态里可以少一维判断。合并的思路是:把每个儿子的子树看成一个物品组,这个组里的物品体积可以取0到size[v],你要往u已有的容量里塞。合并公式是:dp[u][j] max(dp[u][j], dp[u][j-k] dp[v][k])其中k是分给儿子v子树的节点数。这个式子和背包问题几乎一模一样,所以叫树上背包。具体细节和复杂度我在第3节展开,这是树形DP里最容易翻车的一块。2.3 路径型状态树直径的合并思路还有一类问题问的是路径,比如树的直径、树上的最长路、经过某点的最长链。这类问题的状态不再是选几个,而是从某个点往下走的最长路径。以树直径为例,定义down[u]为从u出发,往下走(只走子树方向)能到达的最远距离。那么经过u的最长路径,就是u的两个不同儿子的down值相加(还要加上两条边的权),取所有u中最大的那个就是直径。转移时:ans max(ans, down[u] down[v] w(u,v)); down[u] max(down[u], down[v] w(u,v));注意这两行的顺序:先用旧的down[u]和当前的down[v]算答案,再更新down[u]。如果顺序反了,可能就用同一个儿子算了两遍,得到一条自我重复的路径。这个先算答案再更新的模式和上一节说的合并顺序是同一个道理,一定要形成肌肉记忆。3. 树上背包把O(n^3)写成O(n^2)的关键3.1 朴素三重循环的复杂度真相很多人第一次写树上背包,看着那个dp[u][j] max(dp[u][j], dp[u][j-k] dp[v][k])的三层循环,第一反应是O(n^3)要炸。但实测下来,标准的树上背包合并其实是O(n^2)的,这个结论值得好好讲清楚,因为很多人是背下来的,并不知道为什么。关键在于那两个循环的边界。当我们在节点u上合并儿子v的时候,枚举的j不是从1到n,而是从1到当前已经合并过的子树总大小,k也只是到size[v]。合并的总代价,等于这对(已经合并的子树,新加入的子树)之间的节点对数量,也就是size_a * size_b量级。把每个节点对(u,x)想象成它们只在它们的最近公共祖先那里被合并一次,所以总的贡献次数是每对点一次,总共O(n^2)。这就是为什么树上背包不要无脑开到n的循环上界,而是严格用当前的size来限制,否则就真的退化成O(n^3)了。3.2 合并顺序与倒序枚举的坑虽然复杂度是O(n^2),但写得不对会错答案。第一个坑是倒序枚举j。这其实和01背包一个道理:我们用的是上一轮DP数组的值来转移,如果正序枚举j,那么本次用到的dp[u][j-k]可能已经包含了对v的合并,相当于一个节点被v用了两次,结果偏大。// 合并儿子 v,倒序枚举容量 j for (int j min(m, size_u size_v); j 1; --j) { for (int k 1; k min(j, size_v); k) { if (j - k 0) continue; dp[u][j] max(dp[u][j], dp[u][j-k] dp[v][k]); } }第二个坑是容量上界的约定。如果状态里包含u自己,那么j至少要留1给u,j-k不能小于1(因为u一定被选)。如果状态不包含u,那就是另一套写法。这个含不含自己必须一开始就定死,中途改会全乱。第三个坑是负权与不可达。如果某些状态根本不可达,dp数组里不该是0,而应该是负无穷,否则在那个非法状态上做加法会得到一个虚假的更优解。我一般初始化成 -INF,只有真正合法的状态才去更新。3.3 完整模板与实测数据下面这个模板是我比赛常用的,状态dp[u][j]表示以u为根选j个节点(u必选)的最大收益:void dfs(int u, int fa) { sz[u] 1; dp[u][1] val[u]; // 只选自己 for (int i head[u]; i; i e[i].nxt) { int v e[i].to; if (v fa) continue; dfs(v, u); for (int j min(m, sz[u] sz[v]); j 1; --j) { for (int k 1; k min(j - 1, sz[v]); k) { if (dp[u][j - k] NEG_INF) continue; dp[u][j] max(dp[u][j], dp[u][j - k] dp[v][k]); } } sz[u] sz[v]; } }实测n3000、mn的随机树,这套写法跑完大概在几十毫秒级,而把j的边界写成n的做法会慢一到两个数量级。差别就在这里。注意:如果题目允许不选任何儿子,记得处理j1时只含自己的情况,循环里k从1开始、j-k1就已经隐含保证了合法性。4. 换根DP当答案对每个节点都问一遍4.1 第一次DFS收集子树信息换根DP解决的是一类很典型的问题:对于树上的每个节点,把它当作根时,某个量是多少。朴素做法是对每个点都跑一次DFS,总复杂度O(n^2),在n到1e6的时候直接超时。换根DP把这个过程压到O(n)。思路分两步。第一次DFS从某个固定根出发,求出每个节点的子树内信息,比如子树大小size[u]、子树内所有点到u的距离之和sub[u]。这一步是标准后序遍历:void dfs1(int u, int fa) { sz[u] 1; sub[u] 0; for (int v : g[u]) { if (v fa) continue; dfs1(v, u); sz[u] sz[v]; sub[u] sub[v] sz[v]; // 边权为1时,加sz[v];带权就加sz[v]*w } }sub[u] sz[v]这一项的含义是:v子树里每个点到u的距离,等于它们到v的距离(sub[v])再加上v到u这一条边,所以多了sz[v]个1。带边权的话那个1换成对应权值。4.2 第二次DFS从父推子的转移推导第二次DFS要算出以每个点为整棵树的根时的答案。设f[u]表示以u为根时,所有点到u的距离之和。我们知道f[root] sub[root]。现在的问题是,已知f[u],怎么求它儿子v的f[v]。当根从u移到v时,整棵树分成两半:v的子树(共sz[v]个点)和其余的点(共n - sz[v]个点)。根移动之后:v子树里的这sz[v]个点,到新根的距离都减少1其余n - sz[v]个点,到新根的距离都增加1所以:f[v] f[u] - sz[v] (n - sz[v]) f[u] n - 2 * sz[v]这就是换根DP最核心的那个转移式。推导不复杂,但一定要自己推一遍,记住这个结论,以后再遇到类似的换根题,直接套这个子树减、其余加的框架。void dfs2(int u, int fa) { for (int v : g[u]) { if (v fa) continue; f[v] f[u] n - 2 * sz[v]; dfs2(v, u); } }4.3 经典题STA-Station与树的重心STA-Station那道题就是标准的换根模板:求以哪个点为根时,所有点的深度之和最大,最后输出那个点的编号。做法就是上面两步,先求size和sub,再换根求f,扫一遍取最大值。树的重心也是换根的思路:重心定义为去掉它之后,最大连通块最小的那个点。可以用一次DFS求出每个点的最大子树和它的向上部分,两者取最大,再对所有点取最小。这里向上部分就是n - sz[u],也是换根思想的体现。换根DP的通用套路我总结成一句:先求子树信息,再用一个已知根(通常是1号点)的全局答案去推所有点。只要你能写出根从u移到v时,哪些点的贡献变了、变了多少,换根就能写。提示:换根的时候注意边权。带权树的转移式会变成f[v] f[u] w * (n - 2 * sz[v]),w是u到v的边权,别漏乘。5. 高频坑位与调试技巧5.1 递归栈溢出与迭代写法树形DP最烦的就是递归深度。链状的树深度是n,如果n到1e5甚至1e6,大概率爆栈。我在本地Windows上测的时候栈小,跑小数据没事,提交上去就RE,排查半天才发现是深度问题。几个应对办法:一是在C提交时手动开栈,或者用局部静态大数组模拟;二是改成显式的迭代写法,先做一次BFS求出后序遍历序列,然后按逆序(也就是后序)处理每个节点,把递归换成循环。迭代版本虽然写起来麻烦,但在面对十万级以上的深链时是保命手段。// 迭代版:先求后序序列,再逆序处理 vectorint order; // BFS 求拓扑序,逆序即为后序 for (int i order.size() - 1; i 0; --i) { int u order[i]; // 在这里用子节点的结果更新 u }5.2 初始化、不可达状态与INF的取法第二个高频错误是初始化。数组开好之后如果不 memset 或者没清干净,上一组测试数据的结果会残留,导致答案莫名其妙偏大。我一般会显式地按size清零,而不是整个数组全清,全清在大数据下反而可能慢。再就是不可达状态。讨论容量维度的时候说过,非法状态要设成负无穷,但要注意加法和取max的过程中别把负无穷再往下传的时候溢出。做法是判断一下:如果参与运算的值是NEG_INF,直接跳过,不要让它参与加法。这个小判断看起来啰嗦,但能省掉一堆WA。5.3 取模与long long溢出如果题目带取模,合并的时候dp[u][j-k] dp[v][k]可能超过模数,先加后模;如果题目不带取模但答案很大,通常要开long long。这里有个隐蔽的坑:在树形DP里,多个子树的结果不断累加,中间值可能超过int,哪怕最终答案在int范围内也可能因为中间过程溢出而算错。保守起见,涉及累加的量都开long long。坑位典型症状解决方式递归爆栈大数据RE,小数据正常开大栈或改迭代状态残留多组数据答案偏大按size精准清零非法状态当0答案大于真实值用负无穷并跳过加法中间溢出小数据对大数据错全用long long合并顺序错答案比标准解大先算答案再更新5.4 多叉树与二叉树的转换要不要做很多老教程会教你左儿子右兄弟把多叉树转成二叉树再DP,那是当年教材的习惯。现在用邻接表存多叉树,递归直接遍历儿子,思路反而更直白,我个人不建议再去做这个转换,除非题目本身就是二叉树的结构(比如二叉苹果树)。二叉苹果树那道题之所以用二叉树,是因为题目给的就是二叉树,直接按左右儿子递归就行,也没必要反过来转成多叉。判断依据很简单:题目给什么结构,你就按什么结构建图,不要人为增加一层转换,那只会让你多写代码、多踩坑。还有个小体会是,写树形DP之前,我习惯先在纸上把状态定义和转移式写出来,尤其是第二维到底代表什么、包含不包含当前节点,想清楚了再动键盘。树形DP的调试成本很高,一旦状态定义错了,改起来往往要重写,不像线性DP那样改个循环边界就完事。把推导做在前面,比对着WA慢慢调要高效得多。