记得第一次接触树形dp是在一场模拟赛里被一道“没有上司的舞会”卡了整整两个小时。当时我以为dp就是线性递推结果题目给了一棵树每个节点有选和不选两种状态父子之间还有约束。后来我才明白树形dp也叫树状dp本质上就是在一棵树上做动态规划把子树当成子问题自底向上合并答案。它不像区间dp那样有明确的左右端点也不像背包dp那样有容量维度而是把树的递归结构直接映射成状态转移。如果你已经会写基础的线性dp、背包dp但一遇到树上问题就不知道状态怎么定义、转移怎么合并那这篇内容就是写给你的。我会从建图、状态设计、递归框架讲起再拆解树形背包、换根dp、树的直径这些高频模型最后把踩过的坑和优化技巧一并整理出来。全文代码以C为主Python也会给关键片段难度覆盖普及组到提高组适合想系统掌握树形dp的算法学习者。1. 树形dp到底在解决什么问题1.1 从线性dp到树形dp的思维跳跃线性dp的典型场景是数组上的递推比如最长上升子序列、01背包状态转移依赖前一个或前几个位置。但树形dp面对的是树结构每个节点可能有多个儿子节点之间没有固定的先后顺序只有父子关系。这时候如果硬套线性dp的“从左到右”思路就会卡在“儿子们怎么合并”这一步。树形dp给出的答案是把每个子树看成一个独立的子问题先递归处理所有儿子得到儿子子树的dp值再在当前节点把这些儿子的信息合并起来。这个“先儿子后父亲”的顺序本质上就是树的后序遍历。举个例子求一棵树的最大独立集每个节点要么选要么不选选了就不能选相邻节点。如果当前节点选那么所有儿子都不能选如果当前节点不选儿子可以选也可以不选。设dp[u][0]表示不选u时以u为根的子树的最大独立集大小dp[u][1]表示选u时的最大值。转移就是dp[u][0] sum(max(dp[v][0], dp[v][1])) // v是u的儿子 dp[u][1] 1 sum(dp[v][0])这个转移没有复杂的顺序问题因为每个儿子只贡献一次。但如果是树形背包儿子们就要按顺序合并类似分组背包。所以树形dp的思维跳跃在于从“考虑前i个元素”变成“考虑前i个儿子”状态维度里往往要带上“当前子树大小”或“已选节点数”。理解这一点之后很多树上问题都能套进同一个框架定义状态、写出基于儿子的转移、后序遍历计算。难点不在于递归而在于状态定义是否覆盖了所有约束以及合并儿子时的复杂度是否可控。1.2 树形dp的核心特征后序遍历与状态合并树形dp最明显的特征就是递归函数通常长这样void dfs(int u, int fa) { // 初始化dp[u] for (int v : g[u]) { if (v fa) continue; dfs(v, u); // 用dp[v]更新dp[u] } }这个框架里dfs(v, u)返回时dp[v]已经计算完毕当前节点只需要把儿子的信息合并进来。合并的方式取决于问题。对于最大独立集合并是直接累加对于树形背包合并是一个二重循环对于换根dp第一次dfs求子树信息第二次dfs求全局信息。后序遍历保证了每个节点被访问一次每条边被访问两次无向图所以基础复杂度是O(n)。但合并儿子时如果处理不当复杂度会飙升。比如树形背包如果每次合并都遍历整个子树大小朴素写法是O(n^2)到O(n^3)需要用到上下界优化才能降到O(n^2)。这也是树形dp最容易翻车的地方。另一个核心特征是“无根树转有根树”。题目通常给的是无向边我们需要自己选一个根然后按父子关系建立有向的递归结构。选根一般选1号节点或者根据题目要求选。建图时用邻接表递归时传入父节点防止走回头路。如果树很深比如链状树递归可能爆栈这时需要改成迭代写法或者手动开栈。状态合并时还要注意初始化。比如求最小值dp数组要初始化为INF但当前节点本身的“选自己”状态要单独赋值。求最大值时有些状态可能初始为0但如果有负数权值初始为0会出错必须初始为负无穷。这些细节在后文会反复强调。2. 树形dp的通用骨架与实现细节2.1 建图与无根树转有根树树形dp的第一步永远是建图。题目给n个节点n-1条边无向。我们用邻接表存储vectorint g[N]; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); }然后选一个根通常选1。在dfs时传入父节点避免回到父亲void dfs(int u, int fa) { for (int v : g[u]) { if (v fa) continue; dfs(v, u); } }这个写法简单但要注意几个坑如果n很大比如1e5以上且树退化成链递归深度会达到n导致栈溢出。解决办法是加编译指令-Wl,--stack128000000Windows下或者改成迭代。更通用的做法是手动用栈模拟后序遍历或者用BFS得到拓扑序然后逆序处理。如果图中有重边或自环需要特判。但树通常没有。如果题目给的是有向边且保证是树那就不用建双向边直接按方向建图即可。无根树转有根树之后每个节点有了明确的子树。后续所有dp都基于这个有根树。如果题目要求以每个节点为根分别求答案那就需要换根dp这是另一个话题。建图时还要考虑节点编号是否从0开始。如果从0开始根选0父节点初始传-1。不要传0因为0可能是合法节点。这是一个小细节但容易导致死循环。2.2 递归dfs的写法与返回值设计树形dp的递归函数通常有两种设计风格一种是把dp数组作为全局变量dfs只负责计算另一种是dfs返回一个结构体或数组。对于状态较少的情况比如2个状态用全局数组更简单。对于状态较多或需要返回多个值的情况可以返回pair或自定义结构体。以最大独立集为例int dp[N][2]; void dfs(int u, int fa) { dp[u][0] 0; dp[u][1] val[u]; // 节点权值 for (int v : g[u]) { if (v fa) continue; dfs(v, u); dp[u][0] max(dp[v][0], dp[v][1]); dp[u][1] dp[v][0]; } }这个写法很清晰但要注意dp[u][1]的初始化要加上节点本身的贡献。如果节点权值都是1就初始化为1。如果权值可能为负dp[u][0]初始为0没问题因为不选当前节点子树可以全不选贡献为0但dp[u][1]必须初始为负无穷然后再加上自己的权值否则可能选了一个负权节点反而更差。对于树形背包dp数组通常是二维的dp[u][j]表示以u为根的子树中选了j个节点或容量为j的最优值。初始化时dp[u][1] val[u]然后对每个儿子做分组背包void dfs(int u, int fa) { sz[u] 1; dp[u][1] val[u]; for (int v : g[u]) { if (v fa) continue; dfs(v, u); for (int j min(sz[u], m); j 1; j--) { for (int k 1; k min(sz[v], m - j); k) { dp[u][j k] max(dp[u][j k], dp[u][j] dp[v][k]); } } sz[u] sz[v]; } }这里sz[u]记录子树大小用于限制循环上界这就是上下界优化的雏形。注意j要倒序枚举因为每个儿子只能选一次类似01背包。如果不倒序就会重复选同一个儿子。返回值设计上如果状态是二维数组通常不需要返回直接用全局数组。如果状态是dp[u]为一个vector也可以返回vector但会有拷贝开销不如传引用。2.3 迭代写法与防止爆栈递归写法虽然直观但在深度很大的树上会爆栈。尤其是链状树递归深度等于节点数即使n1e5也可能导致栈溢出。有两种解决方案第一种是手动开大栈空间。在Windows下可以在编译选项加-Wl,--stack128000000在Linux下可以用ulimit -s unlimited。但这依赖环境不适合比赛提交。第二种是改成迭代。具体做法是先用BFS或DFS求出每个节点的父节点和访问顺序得到一个拓扑序列从根到叶子然后逆序遍历这个序列依次用儿子更新父亲。这样就不需要递归了。vectorint order; queueint q; q.push(1); fa[1] 0; while (!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for (int v : g[u]) { if (v fa[u]) continue; fa[v] u; q.push(v); } } // 逆序处理 for (int i order.size() - 1; i 0; i--) { int u order[i]; // 初始化dp[u] for (int v : g[u]) { if (v fa[u]) continue; // 用dp[v]更新dp[u] } }这种写法把递归变成了循环稳定且不会爆栈。缺点是代码稍微长一点而且需要额外存储fa数组和order数组。对于树形背包这种需要合并多个儿子的情况逆序处理时每个节点的儿子已经计算完毕直接合并即可。还有一种情况是树本身是动态的或者需要多次dfs迭代写法需要重新计算order。一般来说如果n不超过2000递归完全够用如果n达到1e5建议用迭代或者手动开栈。我在实际比赛中更倾向于迭代因为不用担心环境问题。3. 经典模型拆解从背包到换根3.1 树形背包有依赖的背包问题树形背包是树形dp里最常考的模型。典型题面有n个物品每个物品有体积和价值物品之间有依赖关系形成一棵树。选一个物品必须先选它的父亲。问容量为m时能获得的最大价值。这就是“有依赖的背包问题”。状态定义dp[u][j]表示以u为根的子树中选了j个物品或体积恰好为j的最大价值。转移时把每个儿子v看作一组物品组内可以选择选0个、1个……但注意选了儿子v就意味着v的子树中选了若干个。所以对每个儿子做一次分组背包。朴素写法的复杂度是O(n * m^2)因为每个节点合并儿子时是二重循环。如果直接写void dfs(int u) { for (int v : g[u]) { dfs(v); for (int j m; j 1; j--) { for (int k 1; k j; k) { dp[u][j] max(dp[u][j], dp[u][j - k] dp[v][k]); } } } }这个复杂度是O(n * m^2)吗实际上如果每个节点都遍历m总复杂度是O(n * m^2)。但通过上下界优化可以降到O(n * m)。具体做法是记录当前子树大小sz[u]循环j只到min(m, sz[u])循环k只到min(sz[v], j)。这样总复杂度是O(n * m)因为每对节点在它们的LCA处合并一次总的合并次数是O(n^2)的但结合m的限制实际是O(n * m)。代码int sz[N], dp[N][M]; void dfs(int u) { sz[u] 1; dp[u][1] val[u]; // 选u本身 for (int v : g[u]) { dfs(v); for (int j min(sz[u], m); j 1; j--) { for (int k 1; k min(sz[v], m - j); k) { dp[u][j k] max(dp[u][j k], dp[u][j] dp[v][k]); } } sz[u] sz[v]; } }注意初始化dp[u][1] val[u]其他为负无穷。如果要求“可以不选任何物品”那么dp[u][0] 0也要初始化。但树形背包通常要求选了父亲才能选儿子所以根节点必须选。如果根节点可以不选那就加一个虚拟根0把真正的根作为它的儿子然后虚拟根的容量为m1最后答案是dp[0][m1]。还有一个常见变种是“每个节点有代价求恰好选m个节点的最小代价”。转移方程类似只是把max改成min。3.2 树的直径与最大独立集树的直径有两种求法两次dfs/bfs或者树形dp。两次bfs更简单但只能求长度不能处理带负权边的情况。树形dp可以处理负权边。树形dp求直径对于每个节点u维护从u向下走的最长路径d1[u]和次长路径d2[u]。遍历儿子v如果d1[v] w(u,v) d1[u]则更新d2[u] d1[u]d1[u] d1[v] w否则如果大于d2[u]更新d2[u]。最终直径是max(d1[u] d2[u])。int d1[N], d2[N], ans; void dfs(int u, int fa) { d1[u] d2[u] 0; for (auto [v, w] : g[u]) { if (v fa) continue; dfs(v, u); int t d1[v] w; if (t d1[u]) { d2[u] d1[u]; d1[u] t; } else if (t d2[u]) { d2[u] t; } } ans max(ans, d1[u] d2[u]); }这个写法的关键是d1和d2的更新顺序。如果先更新d1再更新d2要小心把原来的d1覆盖掉。上面的写法用t临时保存逻辑清晰。最大独立集前面已经讲过这里补充一个变种如果节点有权值且权值可能为负那么dp[u][1]要初始化为val[u]dp[u][0]初始化为0。但要注意如果val[u]是负数选u可能不如不选所以转移时dp[u][0] max(dp[v][0], dp[v][1])而dp[u][1] dp[v][0]。最终答案是max(dp[root][0], dp[root][1])。3.3 换根dp二次扫描与 rerooting换根dp解决的是“以每个节点为根时的答案”这类问题。典型题求每个节点到其他所有节点的距离之和。如果对每个节点都跑一次dfs复杂度O(n^2)太慢。换根dp通过两次dfs第一次求子树信息第二次用父节点的信息更新子节点实现O(n)。以“求每个节点的深度和”为例设down[u]表示以u为根的子树中所有节点到u的距离之和sz[u]表示子树大小。第一次dfs后序遍历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]; // 边权为1 } }第二次dfs前序遍历计算ans[u]表示以u为根时所有节点到u的距离之和。对于根节点1ans[1] down[1]。对于子节点v当根从u换到v时v的子树中所有节点距离减少1其他节点距离增加1。所以void dfs2(int u, int fa) { for (int v : g[u]) { if (v fa) continue; ans[v] ans[u] - sz[v] (n - sz[v]); dfs2(v, u); } }这个转移的核心是ans[v] ans[u] - sz[v] (n - sz[v])。解释一下以u为根时v子树中的节点到u的距离为down[v] sz[v]换根到v后这些节点到v的距离变为down[v]减少了sz[v]而其他节点到u的距离加上边(u,v)后到v的距离增加了n - sz[v]。所以公式成立。换根dp的通用思路是先固定一个根求出每个子树的dp值再从上到下用父节点的答案推导子节点的答案。推导时要注意哪些量是“子树内”的哪些是“全局”的。常见错误是忘记更新sz数组或者在第二次dfs时修改了第一次的dp值导致后续出错。建议把两次dfs分开写第二次只读不写第一次的数组。3.4 最小点覆盖与最大匹配树的最小点覆盖选最少的点使得每条边至少有一个端点被选。树形dp解法dp[u][0]表示不选u时以u为根的子树的最小点覆盖dp[u][1]表示选u时的最小值。转移如果选u儿子可以选或不选dp[u][1] 1 sum(min(dp[v][0], dp[v][1]))如果不选u那么所有儿子必须选dp[u][0] sum(dp[v][1])最终答案是min(dp[root][0], dp[root][1])。树的最大匹配选最多的边使得任意两条边没有公共端点。树形dp解法dp[u][0]表示u不匹配不选与父亲的边时的最大匹配dp[u][1]表示u匹配时的最大匹配。转移稍复杂dp[u][0] sum(max(dp[v][0], dp[v][1]))dp[u][1]需要从儿子中选一个v与u匹配其余儿子取max。可以写成dp[u][1] max(dp[u][0] - max(dp[v][0], dp[v][1]) dp[v][0] 1)。这个转移利用了dp[u][0]作为基础然后减去选中的v原本的贡献再加上dp[v][0] 1。注意dp[v][0]表示v不与u匹配时的最大匹配因为v和u匹配后v不能再和其他儿子匹配所以v的状态是dp[v][0]。这两个模型在树上很常见核心还是状态设计。最小点覆盖的状态只有选和不选最大匹配多了一个“是否与父亲匹配”的维度。理解这些之后遇到类似问题可以快速建模。4. 优化技巧与常见坑4.1 上下界优化与剪枝树形背包的朴素写法是O(n * m^2)但通过上下界优化可以降到O(n * m)。关键是用sz[u]限制循环范围。具体来说合并儿子v时j从min(sz[u], m)倒序枚举到1k从1枚举到min(sz[v], m - j)。这样每个节点对(i, j)只会被合并一次。证明略复杂但结论是总复杂度O(n * m)。除了上下界还可以用“前缀后缀合并”来优化。比如某些问题中合并儿子时的转移是卷积形式可以用前缀和或后缀和加速。但一般树形背包用上下界就够了。剪枝算法在树形dp中也有应用。比如如果某个子树的dp值不可能超过当前最优解可以提前剪枝。但在标准题中上下界优化已经足够剪枝更多用于搜索。另外如果m很大而n很小可以反过来把状态定义为“选了j个节点”而不是“容量为j”。这样复杂度是O(n^2)。所以要根据n和m的大小选择状态定义。如果n1000m1e5那O(n*m)会超时但O(n^2)可以接受。4.2 前缀后缀合并与空间优化有些树形dp需要合并多个儿子的信息且合并操作不满足交换律或结合律。比如求每个节点到其他所有节点的距离之和换根dp可以O(n)。但如果要求“每个节点的子树中距离不超过k的节点个数”就需要在合并儿子时用前缀和。前缀后缀合并的典型场景是对于节点u它的儿子v1, v2, ..., vk我们需要计算某种贡献使得每个儿子都能得到其他儿子的信息。可以先从左到右求前缀dp再从右到左求后缀dp然后对于每个儿子用前缀和后缀合并得到除它以外的信息。这样复杂度O(总儿子数)而不是O(儿子数的平方)。空间优化方面如果dp数组是二维的可以用滚动数组。但树形dp通常每个节点都需要保留dp值因为父节点合并时需要用到所有儿子的dp。如果内存紧张可以用vector动态分配或者用dp[u][j]的大小不超过sz[u]这样总空间是O(n * m)但实际使用量是O(n * m)的稀疏形式。更好的做法是用vectorint dp[N]每个节点的vector大小为sz[u] 1这样总空间是O(n^2)但实际是O(n)的节点数乘以平均大小通常可接受。4.3 常见错误排查表错误现象可能原因排查方法答案偏小dp初始化没有设为负无穷检查求max时是否初始为-INF求min时是否初始为INF递归爆栈树深度太大改用迭代或手动开栈死循环没有判父节点dfs时传入fa遇到fa跳过答案重复计算合并儿子时没有倒序树形背包的j必须倒序枚举复杂度超时没有上下界优化用sz数组限制循环范围换根dp答案错误第二次dfs修改了第一次的数组第二次dfs只读不写用新数组存答案节点权值为负时出错初始化为0导致被迫选负权节点初始化为-INF再赋值多组数据未清空没有重置dp、sz、g每组数据前清空所有数组这个表格里的问题我几乎都踩过一遍。特别是“初始化”和“倒序枚举”新手最容易忽略。另外多组数据时一定要清空邻接表否则会残留上一次的边。还有一个坑是如果题目要求“恰好选m个节点”而某些子树无法凑出m个那么dp值要设为-INF。如果求“最多选m个”则可以用0初始化。区分清楚这两者的区别。5. 实战一道综合题的完整推导5.1 题意与状态定义题目给一棵n个节点的树每个节点有一个权值val[i]可能为负。要求选出一个连通块使得连通块中节点权值之和最大。输出最大和。这是一道经典的“最大权连通子图”问题可以用树形dp解决。状态定义dp[u]表示以u为根的子树中包含u且与u连通的连通块的最大权值和。注意这个连通块必须包含u因为如果不包含u那就属于儿子的子树会在儿子的dp中计算。转移对于每个儿子v如果dp[v] 0那么把v的子树并入当前连通块会增大总和所以dp[u] dp[v]否则不并入。最后答案是所有dp[u]中的最大值。这个题的状态很简单但包含了树形dp的核心思想子问题最优解合并。不过这里有一个细节连通块必须包含u所以dp[u]初始为val[u]然后累加正的dp[v]。5.2 转移方程与代码实现#include bits/stdc.h using namespace std; const int N 1e5 10; vectorint g[N]; int val[N], dp[N], ans -1e9; void dfs(int u, int fa) { dp[u] val[u]; for (int v : g[u]) { if (v fa) continue; dfs(v, u); if (dp[v] 0) dp[u] dp[v]; } ans max(ans, dp[u]); } int main() { int n; cin n; for (int i 1; i n; i) cin val[i]; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); cout ans endl; return 0; }这段代码非常短但威力不小。注意ans初始化为-1e9因为节点权值可能全是负数最大和也是负数。如果初始化为0遇到全负就会输出0但题目可能要求必须选至少一个节点。所以初始化要小心。5.3 复杂度与测试复杂度每个节点访问一次每条边访问两次O(n)。空间O(n)。对于n1e5完全没问题。测试时可以用以下数据5 -2 1 3 -1 2 1 2 1 3 2 4 2 5手动计算节点2的子树中4的权值为-1不选5的权值为2选节点2本身为1所以dp[2]123。节点3为3dp[3]3。节点1为-2加上dp[2]3和dp[3]3dp[1]-2334。ansmax(4,3,3,2,-1)4。输出4。正确。如果树是一条链-1 -2 -3那么dp[3]-3dp[2]-2dp[1]-1ans-1。输出-1表示选一个权值最大的单节点。符合预期。这个题还可以扩展如果要求连通块大小不超过k就需要在状态里加一维大小变成树形背包。如果要求连通块必须包含某个特定节点就把根固定为那个节点。如果要求输出方案可以在转移时记录选择。5.4 另一个实战换根dp求距离和为了巩固换根dp再给一道题n个节点的树边权为1求每个节点到其他所有节点的距离之和。输入n和n-1条边输出n个整数。第一次dfs求子树大小和子树内距离和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]; } }第二次dfs求全局答案void dfs2(int u, int fa) { for (int v : g[u]) { if (v fa) continue; ans[v] ans[u] - sz[v] (n - sz[v]); dfs2(v, u); } }主函数中ans[1] down[1]然后dfs2(1, 0)。输出ans[1..n]。这个题的关键是理解ans[v] ans[u] - sz[v] (n - sz[v])的推导。我在第一次写的时候把sz[v]和n - sz[v]搞反了导致答案偏大。后来画了个图才明白换根后v子树内的节点距离减少1所以减去sz[v]v子树外的节点距离增加1所以加上n - sz[v]。记住这个口诀子树内减子树外加。对于带边权的树公式变为ans[v] ans[u] - (down[v] sz[v] * w) (n - sz[v]) * w其中w是边(u,v)的权值。可以自行推导。6. 树形dp的常见变种与延伸6.1 基环树上的dp基环树就是一棵树加上一条边形成一个环。处理基环树上的dp通常先找到环把环上的边断开然后对环上的每个点分别做树形dp最后在环上做一次环形dp。比如“没有上司的舞会”的基环树版本需要枚举环上第一个点选或不选分别做两次dp。找环的方法拓扑排序入度为1的点入队最后剩下的点就是环上的点。或者用并查集找环。断开环后对每个环上的点把它的子树不包括环上的其他点做树形dp得到每个点的两种状态值然后在环上做线性dp。6.2 树上依赖背包的变种除了标准的树形背包还有“每个节点可以选择多个物品”的变种或者“父子依赖但可以跳过父亲”的变种。前者需要把节点拆成多个物品后者可以加虚拟根。还有一种“树上分组背包”每个节点有多个物品选一个物品必须先选父亲但每个节点只能选一个物品。这种问题需要把每个节点的物品看作一组在合并儿子时处理。6.3 树形dp与状态压缩如果树上的状态很少可以用状态压缩来简化。比如每个节点有3种颜色求染色方案数使得相邻节点颜色不同。可以用dp[u][c]表示u染成c的方案数转移时枚举儿子颜色。如果状态更多可以用位运算压缩。但树形dp本身的状态维度通常不高除非有额外的约束。6.4 树形dp的调试技巧调试树形dp时最有效的方法是打印中间状态。对于小数据可以在dfs中输出每个节点的dp值然后手动验证。对于大数据可以写一个暴力程序对拍。暴力程序可以用枚举所有子树或者用递归模拟。另外可以用assert检查数组下标是否越界或者检查dp值是否在合理范围内。还有一个技巧如果答案是错的先检查根节点的dp值再检查叶子节点的dp值。叶子节点的dp通常很简单如果叶子错了那肯定是初始化问题。如果叶子对了父节点错了那就是转移方程写错了。7. 从树形dp看算法学习的通用方法树形dp只是一个缩影。学习任何算法最怕的就是“背模板”。树形dp的模板很简单但题目变化多端。真正要掌握的是“状态定义”和“转移合并”这两个核心。状态定义决定了你能解决什么问题转移合并决定了你的复杂度。每次遇到新题先问自己每个节点的状态是什么儿子如何影响父亲父亲如何影响儿子需不需要换根需不需要考虑子树大小我个人的习惯是拿到一道树上问题先在纸上画一棵三层的树标出每个节点的状态然后手动模拟一遍转移。如果能用手算出来代码就水到渠成了。如果手算都卡住那说明状态定义有问题需要重新思考。另外多写多练是必须的。推荐从“没有上司的舞会”“选课”“二叉苹果树”这些经典题开始然后过渡到换根dp“STACCATO”“POJ 3585”再到基环树“骑士”“岛屿”。每道题都自己先想半小时再看题解然后关掉题解自己写一遍。写完之后对比题解的写法和自己的写法看看哪里可以优化。这样坚持一个月树形dp就不再是拦路虎了。最后再分享一个排查技巧如果树形dp的答案总是差一点检查一下dp[u][1]的初始化是否加上了节点自身的贡献。很多人在合并儿子时忘了把自己算进去导致答案偏小。还有如果题目要求取模记得在每次加法后取模不要等到最后。负数取模要加模数再取模。这些小细节往往就是AC和WA的区别。