◎学完你会
- 理解树形 DP 的基本套路：状态挂在节点上，子树先算完再合并到父亲；
- 会写
dfs(u, fa) 后序遍历 + dp[u] 转移，处理"选 / 不选"这类二元状态；
- 知道换根 DP：一次预处理 + 一次 DFS，求出"以每个点为根"的答案。
1树上状态转移：自底向上
树是无环的，所以不存在"状态成环"的问题——这正是树形 DP 好写的原因。以经典题 树的最大权独立集（相邻节点不能同时选）为例：每个节点两个状态，dp0[u]=不选 u 时子树最优，dp1[u]=选 u 时子树最优。
// 后序遍历：先递归儿子，再合并到自己
void dfs(int u, int fa) {
dp0[u] = 0; dp1[u] = w[u]; // 初值：自己这个点
for (int v : g[u]) if (v != fa) {
dfs(v, u);
dp0[u] += max(dp0[v], dp1[v]); // 不选 u，儿子随意
dp1[u] += dp0[v]; // 选 u，儿子都不能选
}
}
// 答案 = max(dp0[root], dp1[root])
| 节点 | 子节点 | dp0 | dp1 |
|---|
| 4 | — | — | — |
| 5 | — | — | — |
| 2 | 4,5 | — | — |
| 6 | — | — | — |
| 3 | 6 | — | — |
| 1 | 2,3 | — | — |
权值 w = [_,10,5,8,3,4,6]，树为 1-{2,3}、2-{4,5}、3-{6}。点「下一步」按后序出值。
顺序是关键：后序（先儿子后自己）才能保证算 dp[u] 时子树全算完。用 dfs(u,fa) 传父节点防止"走回头路"。
2关键命令与换根 DP
| 要点 | 含义 / 写法 |
|---|
| 建树 | 邻接表 vector<int> g[N]，无向边加两次，递归时用 fa 剪枝 |
| 状态设计 | dp0[u] / dp1[u]：二元状态最常见；也有 dp[u][j]（容量/个数） |
| 合并（后序） | dp[u] = Σ f(dp[child])，遍历子节点累加 |
| 换根 DP | 第一遍求子树的 down[]，第二遍用父亲答案反推 up[]，ans[u]=down[u]+up[u] |
| 树的直径 | 两次 DFS/BFS：从任意点找最远点 A，再从 A 找最远点 B，AB 即直径 |
// 换根 DP 骨架：求"每个点到其他所有点的距离和"（两遍 DFS）
void dfs1(int u, int fa) { // 子树内距离和 + 子树大小
sz[u] = 1; down[u] = 0;
for (int v : g[u]) if (v != fa) {
dfs1(v, u);
sz[u] += sz[v];
down[u] += down[v] + sz[v]; // 每条边贡献 sz[v] 次
}
}
void dfs2(int u, int fa) { // 用父亲结果推自己
for (int v : g[u]) if (v != fa) {
up[v] = up[u] + (n - sz[v]) + (down[u] - down[v] - sz[v]);
dfs2(v, u);
}
}
✳跨学科：自底向上的汇总
树形 DP 的"先算下级、再汇总到上级"几乎就是组织管理的算法版本：公司的报销要等部门汇总、部门要等小组汇总；财务报表也是层层向上合并。理解了"后序合并"，你也就理解了层级结构里数据是怎么流动的。
⚠易错点
遍历顺序错：用"前序"或者先算 dp[u] 再去递归儿子，会用到来算完的子树值。必须先递归、后合并。
链状树爆栈：N=2e5 且树退化成链时，递归深度 = N，默认栈会 RE。竞赛里常见做法是把大数组开全局（别开在函数里），必要时改迭代或加 -Wl,--stack。
vis 数组误用：树上不需要 vis，用 fa 参数防回走即可；混用 vis 容易漏遍历或多遍历。
换根加减不对称：从父亲推儿子时，要把"这条子树"的贡献先减掉再加上另一端，漏掉 (n - sz[v]) 是经典错误。
✎练一练
用递归写树形 DP 时，正确的求值顺序是？
合并 dp[u] 时要用到子树的完整结果，所以必须先递归儿子（后序遍历）。编号顺序对树的结构没有意义。
题目要求：对树上的每一个点，求"以它为根时的答案"（如到其他所有点距离之和、最小深度和）。应该怎么做？
这类"每个点当根"的题目，最合适的做法是？
换根 DP 用两遍 DFS 把 O(n²) 降到 O(n)：第二遍把"父亲作为一个整体"的贡献替换进来。暴力做法多数题会 TLE。
给一棵 N 个点的树（边权为正），求任意两点间距离的最大值（直径）。
求树的直径，最简洁的正确做法是？
两次 DFS/BFS：第一次从任意点出发找最远点 A（A 必为直径端点之一），第二次从 A 找最远点 B，距离即直径，复杂度 O(n)。