换根 DP（树中距离之和）
动态规划 · 二次扫描 · 每个点都当一次根
每个点都要答案
求树上每个节点到其余所有点的距离之和。树形 DP 固定一个根算一次没问题，可这里 n 个点都要——逐点重跑就是 O(n²)。本页的树：
0 ← 先当根
/ \
1 2
/ \
3 4换根：账本不用重记，挪一格改两笔
第一趟（后序）：老老实实算出每个点的 size（子树大小）和 down（到子树内所有点的距离和），顺手得到根的答案 ans[0] = down[0]。第二趟（前序）：根从 u 挪到相邻的 v——v 子树里 size[v] 个点近了 1 步、其余 n − size[v] 个点远了 1 步：ans[v] = ans[u] − size[v] + (n − size[v])。一步 O(1)，全树 O(n)。下表三列逐格点亮，黄格是每一步引用的账本。右侧代码随每一步同步高亮。
| size | down | ans | |
|---|---|---|---|
| 0·根 | |||
| 1·L | |||
| 2·R | |||
| 3·LL | |||
| 4·LR |
求「树上所有点到 u 的距离和」——每个 u 都要！逐点 BFS 是 O(n²)。换根 DP 二次扫描：第一趟后序算「子树内」（size 与 down），第二趟前序把答案从父亲推给孩子，全树 O(n)
1function sumOfDistances(n: number, adj: number[][]): number[] {
2 const size = new Array(n).fill(1);
3 const down = new Array(n).fill(0);
4 const ans = new Array(n).fill(0);
5 const dfs1 = (u: number, p: number): void => { // 第一趟：后序
6 for (const v of adj[u]) if (v !== p) {
7 dfs1(v, u);
8 size[u] += size[v];
9 down[u] += down[v] + size[v]; // 孩子子树整体抬 1 步
10 }
11 };
12 const dfs2 = (u: number, p: number): void => { // 第二趟：前序换根
13 for (const v of adj[u]) if (v !== p) {
14 ans[v] = ans[u] - size[v] + (n - size[v]); // 近 size[v] 远 n−size[v]
15 dfs2(v, u);
16 }
17 };
18 dfs1(0, -1);
19 ans[0] = down[0]; // 第一趟收官：根的答案
20 dfs2(0, -1);
21 return ans;
22}
树0 根；1,2 为子；3,4 为 1 的子
目标ans[u] = Σ dist(u, ·)，全部 5 个
1 / 12
换根三件套
①第一趟后序：把「子树内」的信息算干净（size / down / 子树最远……）。
②可增量修正：答案对「根挪一步」能 O(1) 修正——距离和的近远账、最值的换根合并。
③第二趟前序：沿树把修正传下去，每点各得其所。
坑：第二趟必须用父亲已换根后的答案推孩子（前序），别用第一趟的旧值。
②可增量修正：答案对「根挪一步」能 O(1) 修正——距离和的近远账、最值的换根合并。
③第二趟前序：沿树把修正传下去，每点各得其所。
坑：第二趟必须用父亲已换根后的答案推孩子（前序），别用第一趟的旧值。
同款还有：树的中心（最远距离最小的点）、每点的最远节点（向上/向下两条最长路合并）、834 距离之和原题。至此 DP 大类十一页真收官：序列、区间、集合、树、数位五种状态设计，外加「一趟不够就两趟」的换根——动态规划的常用武器全部上墙。