一、树形 DP 的基本姿势
树没有环，天然适合递归：每个节点的答案只由它的子树决定。后序遍历（先处理完所有儿子再处理父亲）就能自底向上完成 DP：
dfs(u)：对每个儿子 v 先 dfs(v)，再用 v 的结果更新 u 的状态
生活类比：公司统计每个部门的总人数。总经理不用逐个数员工——每个主管先报上自己部门的人数，上级把下级汇报的数字加起来再加自己即可。这就是一次树形 DP。
二、经典应用：树的重心（P1395 会议）
定义：删掉节点 u 后，剩下的若干连通块中最大的那块越小越好。使"最大连通块大小"最小的 u 称为树的重心。会议室选址、网络中心部署都是这个模型。
删去 u 后连通块分两类：每个儿子的子树（大小 sz[v]），以及"u 上方的其余部分"（大小 n − sz[u]）。所以：
maxPart(u) = max( 所有儿子的 sz[v], n − sz[u] )，取 maxPart 最小的 u
一次 dfs 求出所有 sz 即可，O(n)。性质：重心最多 2 个，且若有两个必相邻（题目常要求输出编号最小的那个）。
三、换根 DP：每个点都当一次"根"
问题形态：对每个节点 u，求"以 u 为中心"的某个量（如 u 到所有点的距离和）。对每个 u 单独 dfs 一遍是 O(n²)，换根 DP 用两次 dfs 做到 O(n)。
距离和的换根公式
设 f[u] = u 到全树所有点的距离和。当根从 u 移到儿子 v 时（边长为 1）：
- v 的子树里 sz[v] 个点，每个到 v 比到 u 近 1；
- 其余 n − sz[v] 个点，每个到 v 比到 u 远 1。
f[v] = f[u] + (n − sz[v]) − sz[v] = f[u] + n − 2·sz[v]
两次 dfs 框架
- 第一遍 dfs（自底向上）：求出每个子树大小 sz 和以 1 为根的 f[1]。
- 第二遍 dfs（自顶向下）：从根出发，用换根公式把 f 推给每个儿子。
数字走查：链 1—2—3（n = 3，边长 1）
四、模板代码（距离和）
void dfs1(int u, int fa) {
sz[u] = 1;
for (int v : g[u]) if (v != fa) {
dfs1(v, u);
sz[u] += sz[v];
f[1] += dep[v]; // f[1] = 所有点深度和（根到各点距离和）
}
}
void dfs2(int u, int fa) {
for (int v : g[u]) if (v != fa) {
f[v] = f[u] + n - 2 * sz[v]; // 换根公式
dfs2(v, u);
}
}推广：换根不止用于距离和。凡是"答案能拆成 子树内贡献 + 子树外贡献"的量（如 P3047 求每个点 k 步内的权和），都可用"第一遍统计子树内 f[u][j]、第二遍补子树外 g[u][j]"的二次扫描法。
五、易错点清单
- 换根公式里 sz[v] 是以全局根（第一次 dfs 的根）为参照的子树大小，换根过程中 sz 不变——别在第二遍 dfs 里重算。
- 距离和、路径计数等累加量容易超 int，用
long long。 - 无根树先任选一个点当根（通常 1 号），dfs 记得传父节点防回头。
- n 到 105 以上时递归可能爆栈：加深栈或改迭代（本地测不出，评测机上翻车最常见）。
六、练习
- P1395 会议（树的重心）
- P3047 Nearby Cows（二次扫描：子树内 + 子树外）
- 真题对照：CSP-S 2023 T4 种树、2022 T2 数据传输