企业官网建设流程全解析

记得第一次接触树形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条边，无向。我们用邻接表存储：

vector<int> 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,--stack=128000000（Windows下）或者改成迭代。更通用的做法是手动用栈模拟后序遍历，或者用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 迭代写法与防止爆栈

递归写法虽然直观，但在深度很大的树上会爆栈。尤其是链状树，递归深度等于节点数，即使n=1e5也可能导致栈溢出。有两种解决方案：

第一种是手动开大栈空间。在Windows下，可以在编译选项加-Wl,--stack=128000000；在Linux下，可以用ulimit -s unlimited。但这依赖环境，不适合比赛提交。

第二种是改成迭代。具体做法是先用BFS或DFS求出每个节点的父节点和访问顺序，得到一个拓扑序列（从根到叶子），然后逆序遍历这个序列，依次用儿子更新父亲。这样就不需要递归了。

vector<int> order; queue<int> 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，把真正的根作为它的儿子，然后虚拟根的容量为m+1，最后答案是dp[0][m+1]。

还有一个常见变种是“每个节点有代价，求恰好选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的距离之和。对于根节点1，ans[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)倒序枚举到1，k从1枚举到min(sz[v], m - j)。这样每个节点对(i, j)只会被合并一次。证明略复杂，但结论是总复杂度O(n * m)。

除了上下界，还可以用“前缀后缀合并”来优化。比如某些问题中，合并儿子时的转移是卷积形式，可以用前缀和或后缀和加速。但一般树形背包用上下界就够了。

剪枝算法在树形dp中也有应用。比如如果某个子树的dp值不可能超过当前最优解，可以提前剪枝。但在标准题中，上下界优化已经足够，剪枝更多用于搜索。

另外，如果m很大而n很小，可以反过来把状态定义为“选了j个节点”，而不是“容量为j”。这样复杂度是O(n^2)。所以要根据n和m的大小选择状态定义。如果n=1000，m=1e5，那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)的稀疏形式。更好的做法是用vector<int> dp[N]，每个节点的vector大小为sz[u] + 1，这样总空间是O(n^2)但实际是O(n)的节点数乘以平均大小，通常可接受。

4.3 常见错误排查表

这个表格里的问题我几乎都踩过一遍。特别是“初始化”和“倒序枚举”，新手最容易忽略。另外，多组数据时一定要清空邻接表，否则会残留上一次的边。

还有一个坑是：如果题目要求“恰好选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; vector<int> 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)。对于n=1e5，完全没问题。测试时可以用以下数据：

5 -2 1 3 -1 2 1 2 1 3 2 4 2 5

手动计算：节点2的子树中，4的权值为-1，不选；5的权值为2，选；节点2本身为1，所以dp[2]=1+2=3。节点3为3，dp[3]=3。节点1为-2，加上dp[2]=3和dp[3]=3，dp[1]=-2+3+3=4。ans=max(4,3,3,2,-1)=4。输出4。正确。

如果树是一条链：-1 -2 -3，那么dp[3]=-3，dp[2]=-2，dp[1]=-1，ans=-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的区别。