引言动态规划DP是算法竞赛中最灵活也最强大的工具之一。当DP遇到树这种数据结构时就诞生了树形DP——在树上做动态规划。树形DP的基础模型很简单从叶子节点向上递推用子节点的信息更新父节点。但实际题目往往不会这么直接——“求树上距离每个节点最远的节点”“在树上做背包选课”“每个节点都可以作为根求全局最优”……这些进阶问题需要更精巧的DP设计。本文将从树形DP的基础出发重点讲解两个进阶方向树上背包在树上做分组背包和换根DP让每个节点都成为根求全局最优。如果把基础树形DP比作“从树叶到树根收集信息”那么树上背包就是“在收集信息时还要做选择”而换根DP则是“不仅要从下往上收集还要从上往下传递”。三种能力合在一起才能应对树上DP的全部挑战。前置知识在学习树形DP进阶之前你需要掌握以下基础树的基本概念节点、边、根、子树、叶子节点。深度优先搜索DFS树形DP的核心遍历方式。基础树形DP如“没有上司的舞会”——每个节点选或不选用子节点更新父节点。背包DP0/1背包、分组背包的基本概念。递归与记忆化树形DP通常用递归实现。第一章树上背包——在树上“选课”1.1 问题引入有依赖的背包普通的背包问题是有若干个物品每个物品有重量和价值在容量限制下选择物品使总价值最大。树上背包在此基础上增加了一个约束物品之间存在依赖关系——要选择某个物品必须先选择它的父节点。最经典的例子是“选课”每门课可能有先修课要选“数据结构”必须先选“程序设计基础”。如果把课程之间的依赖关系画成一棵树问题就变成了“在树上选择若干节点必须选父节点才能选子节点”。1.2 状态设计设dp[u][j]表示在以节点u为根的子树中选择j个节点且必须选择u本身所能获得的最大价值。关键约束因为必须选u才能选子树中的其他节点所以dp[u][j]中j至少为1至少选u自己。1.3 转移方程对于节点u我们逐个处理它的每个子节点v像做分组背包一样把子树的“选课方案”当作一组物品text初始化 dp[u][1] val[u]只选u自己 对于每个子节点 v 对于 j 从 m 到 1当前已选的课程数倒序 对于 k 从 1 到 size[v]在v的子树中选k门课 dp[u][jk] max(dp[u][jk], dp[u][j] dp[v][k])代码框架cppvoid dfs(int u, int fa) { sz[u] 1; dp[u][1] val[u]; // 只选自己 for (int v : children[u]) { if (v fa) continue; dfs(v, u); // 背包合并倒序枚举容量 for (int j min(m, sz[u]); j 1; j--) { for (int k 1; k sz[v] j k m; k) { dp[u][jk] max(dp[u][jk], dp[u][j] dp[v][k]); } } sz[u] sz[v]; } }1.4 复杂度分析树上背包的时间复杂度是O(n·m²)在最坏情况下但实际运行中由于每次合并两个子树总复杂度通常为O(n·m)每个节点对在容量维度上被考虑一次。1.5 经典例题洛谷 P2014 选课题目描述有n门课每门课有学分有些课有先修课最多一门。在最多选m门课的条件下如何选课使总学分最大解题思路构建树每门课是一个节点先修课是父节点。如果有多棵树森林添加一个虚拟根节点0学分0将森林变成一棵树。运行树上背包答案就是dp[0][m1]因为虚拟根节点也占了一门课。核心代码来自cpp// dp[x][j]在以x为根的子树中选j门课的最大学分 // 转移将子节点y的子树作为一个分组做分组背包 for (int j m; j 0; j--) { for (int k 1; k sz[y]; k) { if (j k m) { dp[x][jk] max(dp[x][jk], dp[x][j] dp[y][k]); } } }第二章换根DP——让每个节点都成为“根”2.1 问题引入不定根的最优解很多树形DP问题会问“对于树上的每个节点求以该节点为根时的某个答案”。最朴素的做法是枚举每个节点作为根分别做一次树形DP时间复杂度O(n²)。当n达到10⁵时这显然不可行。换根DP也称二次扫描法通过两次DFS将复杂度优化到O(n)第一次DFS任选一个根如节点1计算以它为根的答案。第二次DFS利用父节点的答案推导出子节点作为根时的答案。如果把基础树形DP比作“从下往上递推”换根DP就是“先从上往下推一次再从下往上推一次两次信息合在一起才是完整答案”。2.2 换根DP的核心思想换根DP的关键是理解当根从父节点u转移到子节点v时答案会发生什么变化对于大多数问题变化只涉及两部分v的子树所有节点的深度都减少1因为根下移了一层。v的子树之外所有节点的深度都增加1因为离根远了一层。如果能快速计算出这两个部分的贡献就能在O(1)时间内从ans[u]推导出ans[v]。2.3 经典例题洛谷 P3478 STA-Station题目描述给定一棵n个节点的树求一个节点使得以该节点为根时所有节点的深度之和最大。解题思路第一次DFS计算基础信息任选1为根。计算每个节点的子树大小sz[u]。计算以1为根时的深度之和sum[1]。第二次DFS换根转移假设已知以u为根的深度之和sum[u]。当根从u转移到子节点v时v的子树大小sz[v]中所有节点的深度都减少1。其他节点数量n - sz[v]的深度都增加1。因此转移公式为sum[v]sum[u]−sz[v](n−sz[v])sum[v]sum[u]−sz[v](n−sz[v])化简得sum[v]sum[u]n−2×sz[v]sum[v]sum[u]n−2×sz[v]代码框架cppvoid dfs1(int u, int fa) { sz[u] 1; for (int v : children[u]) { if (v fa) continue; dfs1(v, u); sz[u] sz[v]; sum[1] sz[v]; // 以1为根时每条边对深度的贡献 } } void dfs2(int u, int fa) { for (int v : children[u]) { if (v fa) continue; sum[v] sum[u] n - 2 * sz[v]; // 换根转移 dfs2(v, u); } }最终sum[i]就是以i为根时的深度之和取最大值对应的节点就是答案。2.4 换根DP的通用模板换根DP的通用思路可以总结为第一次DFS计算每个节点的子树信息大小、贡献等。第二次DFS从父节点向子节点转移用ans[fa]推导ans[child]。思考换根DP时问自己两个问题根节点的答案如何计算第一次DFS怎么将答案从父亲传向儿子第二次DFS第三章树形DP进阶的综合应用3.1 树上背包 换根DP有些题目会同时用到树上背包和换根DP。例如“对于每个节点求以该节点为根时在树上做背包的最优值”。思路是先任选一个根做树上背包得到dp[root]。用换根DP的思想将dp信息从父节点传递到子节点。对每个节点合并“来自父节点方向”和“来自子树方向”的信息。3.2 常见题型速查题型核心方法典型例题树上选点选/不选基础树形DPP1352 没有上司的舞会树上背包选课树上背包P2014 选课每个节点作为根的最优值换根DPP3478 STA-Station树上距离最远点换根DP维护最长/次长链P10962 Computer树上染色 / 边权贡献树上背包 特殊贡献计算[HAOI2015] 树上染色总结树形DP的进阶之路可以概括为三个层次层次能力代表技术第一层从叶子向根递推基础树形DP选/不选第二层在递推时做选择树上背包分组背包合并第三层让每个节点都能成为根换根DP两次扫描学习树形DP进阶的三个关键点理解树上背包的“分组”本质每个子树是一组物品在父节点做分组背包合并。掌握换根DP的“两次扫描”套路第一次从下往上第二次从上往下。学会分析“换根时的变化量”根从父节点转移到子节点时哪些部分的贡献变了变化量是多少