换根 DP

代码模板

换根 DP 先任选一点算出一份答案，再沿父子边用“这条边两侧规模之差”推出的增量得到所有根的答案，两次 DFS 就能求出全树每个点作为根时的值。

  • 图论
  • 树
  • 树形DP
  • 换根 DP
前置知识

一句话算法

先随便选一个根，把“根在这个点”的答案算出来；再把根沿着一条边挪到相邻点，用“这条边两侧的规模”推出新答案。两次 DFS，全树每个点作为根的答案都有了。

什么时候需要换根

有的题目要的不是“哪一点最好”，而是每个点作为根时的一份值：

  • 求每个点的“所有点到它距离之和”，再取最小（luogu-P1364、luogu-P1395）；
  • 求每个点作为根时的“所有点深度之和”，取最大（luogu-P3478）；
  • 求每个点到其它点的最远距离，也就是它的偏心距（树的中心的基础）；
  • 求每个点周围某一圈的信息，例如距离不超过 KK 的点权和（luogu-P3047）。

最直接的做法是对每个点各跑一次 DFS，O(n)O(n) 一遍、nn 个点，总共 O(n2)O(n^2)。但相邻两个根之间并没有那么大差别：把根从 uu 挪到它的邻居 vv，只有这条边两侧的点距离会变，一侧全体减一、另一侧全体加一。

换根 DP 做的就是把这个差别写成闭式，于是每个点只花 O(1)O(1) 就从上一次的结果算出自己的结果。

从“重算一遍”到“改一笔”

先把记号固定下来。任选 1 为根，S(v)S(v) 表示以 vv 为根的子树的规模（子树点数、子树点权和、子树最深链……按题目取），WW 是全树的规模。

以加权距离和为例：D(u)=∑xwx⋅dist⁡(x,u)D(u)=\sum_x w_x\cdot\operatorname{dist}(x,u)。把根从 uu 挪到儿子 vv：

  • vv 子树里的点，原来要先走到 vv 再绕到 uu，现在少走一步；
  • 其余的点，原来到 uu 就停，现在要多跨一条边。

两侧人数分别是 S(v)S(v) 和 W−S(v)W-S(v)，于是

D(v)−D(u)=−(S(v))+(W−S(v))=W−2S(v) D(v)-D(u)=-\big(S(v)\big)+\big(W-S(v)\big)=W-2S(v)

这个式子里只有 WW 和 S(v)S(v)，都是“一条边两侧的规模”。只要子树信息在手上，一条边就是一次加减法。

与树的重心、树的中心不是一回事

  • 让加权距离和最小的点叫带权重心，求法见 树的重心；
  • 让“最远距离”最小的点叫树的中心，求法见 树的中心。

这两篇解决的是“找出那个点”。换根 DP 解决的是“求每个点的值”，重心和中心往往只是它算完一遍之后顺带扫出来的结论。方向上的对偶也有趣：重心关心“两侧各有多少人”，中心关心“最远的那一头有多远”。

两次 DFS 的框架

不管转什么量，骨架都是两次遍历，顺序不能反：

  1. 后序 DFS（求子树信息）：定根，回溯时把儿子的信息合并到父亲，得到每个点的 SS，同时直接算出根自己的答案（例如根的答案 =∑xwx⋅dep⁡(x)=\sum_x w_x\cdot \operatorname{dep}(x)）。
  2. 前序 DFS（换根递推）：从根往下走，父亲算完了才轮到儿子，用一条边的增量写出儿子的答案。
第一次 DFS（后序）              第二次 DFS（前序）
  叶子 → 根：攒 S(v)              根 → 叶子：攒 ans(v)
  顺手得到 ans(root)             ans(v) = ans(u) + 增量(u → v)

如果反过来先换根再求子树，儿子拿到的还是没算完的子树信息；如果第二次改成后序，父亲自己也没定值。这个顺序错误在代码里不会报错，只会算出无意义的大数。

三类常见转移

换根 DP 的变体多，卡点几乎都在“增量怎么写”。按被转移的量分三类。

求和型：增量和两侧规模差成正比

代表是距离和、深度和。上面已经推过：

ans⁡(v)=ans⁡(u)+W−2S(v) \operatorname{ans}(v)=\operatorname{ans}(u)+W-2S(v)

无权版把点权全当 11，W=nW=n、S(v)S(v) 是子树点数，于是变成 ans⁡(v)=ans⁡(u)+n−2subtree_size⁡(v)\operatorname{ans}(v)=\operatorname{ans}(u)+n-2\operatorname{subtree\_size}(v)。luogu-P1364、luogu-P1395、luogu-P3478 都是这一条式子，区别只在“权值指什么”“取最小还是取最大”。

这类题唯一要小心的是数值范围：点权和 ×\times 距离容易超过 int，直接用 long long。

最值型：要“换出半边”，所以得存次大值

求和型的增量是两个数相加，天然可减；最值型不行。求每个点的偏心距（到其它点的最远距离）时，需要把两个方向合起来：

ecc⁡(u)=max⁡(子树内最远⏟down⁡(u), 往父亲方向最远的⏟up⁡(u)) \operatorname{ecc}(u)=\max\big(\underbrace{\text{子树内最远}}_{\operatorname{down}(u)},\ \underbrace{\text{往父亲方向最远的}}_{\operatorname{up}(u)}\big)

down⁡(u)\operatorname{down}(u) 第一次 DFS 就得到了。麻烦在 up⁡(v)\operatorname{up}(v)：从 vv 出发往上走，先到 uu，再从 uu 继续走一条不经过 vv 子树的最长路。

graph TD
    P["u 的父亲方向：up(u)"] --- U["u"]
    U --- V["v（要算 up(v) 的点）"]
    U --- S["u 的其它儿子 c：down(c) + 1"]
    V --- D["v 的子树：down(v)，不能用"]

uu 手上“可用的最长路”集合 = { up⁡(u)\operatorname{up}(u) } ∪ { 每个儿子的 down⁡+1\operatorname{down}+1 }。给 vv 传递时要把 vv 自己那一份踢掉：如果 vv 恰好提供了最长的那条，就只能改用次长的那条。所以每个点要记最大和次大两个值（来自不同的儿子），然后

up⁡(v)=1+max⁡(up⁡(u), 不含 v 的最长 down⁡+1) \operatorname{up}(v)=1+\max\big(\operatorname{up}(u),\ \text{不含 } v \text{ 的最长 }\operatorname{down}+1\big)

只存最大值会算错

只记最大值、遇到“最大值来自 vv 自己”就退化成 00，会把答案算大。次大值不是优化，是正确性的一部分。

计数型：增量的写法是容斥

luogu-P3047 要求每个点周围距离不超过 KK 的点权和。设 f(u,k)f(u,k) 表示子树内与 uu 距离恰为 kk 的点权和（f(u,0)=wuf(u,0)=w_u），第二遍 DFS 把“全树版本” g(v,k)g(v,k) 推出来：

g(v,k)=f(v,k)+(g(u,k−1)−f(v,k−2)) g(v,k)=f(v,k)+\big(g(u,k-1)-f(v,k-2)\big)

减去的 f(v,k−2)f(v,k-2) 是容斥：g(u,k−1)g(u,k-1) 里已经含了“从 uu 往 vv 方向走 k−1k-1 步”的点，而它们正是 vv 子树内距离 vv 为 k−2k-2 的那批，重复算了一次（k≤1k\le 1 时那一项按 00 处理）。最后把 k=0∼Kk=0\sim K 加起来就是答案。

计数型的通用套路是：先在后序里把子树内的分布算清楚，再在前序里用父亲的“全树答案”减去“自己子树那份”。增量不一定简单，但只要“能减掉自己那一份”，换根就成立。

复杂度分析

  • 时间复杂度：O(n)O(n)。第一次 DFS 每条边处理一次，第二次 DFS 每条边也是常数次；计数型带一个 KK，是 O(nK)O(nK)。
  • 空间复杂度：O(n)O(n)。子树信息、答案数组和递归栈都是线性的；计数型是 O(nK)O(nK)。

和“每个点重新扫一遍”的 O(n2)O(n^2) 相比，省下来的正是“重复计算了 n−1n-1 次公共部分”。

代码模板

求和型：求每个点作为根时的加权距离和，点权放在 weight[]，无权版全填 1。

C++
cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

        #include <algorithm>
#include <vector>

const int maxn = 1e6 + 5;
using ll = long long;

// 全局邻接表：无向无权树，向 tree[u] 加边 tree[u].push_back(v) 和 tree[v].push_back(u)
using Graph = std::vector<int>;
Graph tree[maxn];
ll weight[maxn];  // weight[u]：点权；无权版全部填 1

// 换根 DP（求和型）：求每个点作为根时的加权距离和 Σ weight[x] * dist(x, u)。
// 用法：
// 1. 读入 n 与边，填好 weight[1..n]；
// 2. TreeRerootSum solver(n);
// 3. const std::vector<ll>& ans = solver.solve(1);  // ans[u] 就是以 u 为根时的答案
struct TreeRerootSum {
    int n;
    int root;               // 第一次 DFS 用的根
    ll total;               // 全树点权和
    std::vector<ll> sub;    // sub[u]：u 子树内的点权和
    std::vector<ll> ans;    // ans[u]：以 u 为根时的加权距离和

    explicit TreeRerootSum(int n) : n(n), root(1), total(0), sub(n + 1), ans(n + 1) {}

    const std::vector<ll>& solve(int start = 1) {
        root = start;
        total = 0;
        for (int u = 1; u <= n; u++) total += weight[u];
        std::fill(ans.begin(), ans.end(), 0);
        dfs_sum(root, 0, 0);
        dfs_reroot(root, 0);
        return ans;
    }

    // 第一次 DFS：统计子树点权和，同时把根的答案直接按深度算出来
    void dfs_sum(int u, int parent, int depth) {
        sub[u] = weight[u];
        ans[root] += weight[u] * depth;

        for (int v : tree[u]) {
            if (v == parent) continue;
            dfs_sum(v, u, depth + 1);
            sub[u] += sub[v];
        }
    }

    // 第二次 DFS：沿父子边递推。根从 u 换到儿子 v 时，
    // v 子树内 sub[v] 个点各少走一步，其余 total - sub[v] 个点各多走一步
    void dfs_reroot(int u, int parent) {
        for (int v : tree[u]) {
            if (v == parent) continue;
            ans[v] = ans[u] + total - 2 * sub[v];
            dfs_reroot(v, u);
        }
    }
};
Python
python 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

        # 依赖模块级全局邻接表 tree：使用前先 tree = [[] for _ in range(n + 1)]，
# 再加无权边 tree[u].append(v) 和 tree[v].append(u)。节点编号 1..n。
# 点权放在模块级 weight 列表里：weight[u] 是 u 的点权，无权版全部填 1。
# dfs 递归深度最坏 n（1e5+），使用前需 sys.setrecursionlimit(1 << 20)。

type Graph = list[list[int]]

tree: Graph = []
weight: list[int] = []


class TreeRerootSum:
    """换根 DP（求和型）：每个点作为根时的加权距离和 Σ weight[x] * dist(x, u)。"""

    n: int
    root: int
    total: int
    sub: list[int]
    ans: list[int]

    def __init__(self, n: int) -> None:
        self.n = n
        self.root = 1
        self.total = 0
        self.sub = [0] * (n + 1)
        self.ans = [0] * (n + 1)

    def solve(self, start: int = 1) -> list[int]:
        """返回 ans 列表：ans[u] 就是以 u 为根时的加权距离和。"""
        self.root = start
        self.total = sum(weight[1 : self.n + 1])
        self.ans = [0] * (self.n + 1)
        self.dfs_sum(self.root, 0, 0)
        self.dfs_reroot(self.root, 0)
        return self.ans

    def dfs_sum(self, u: int, parent: int, depth: int) -> None:
        """第一次 DFS：统计子树点权和，同时把根的答案按深度直接算出来。"""
        self.sub[u] = weight[u]
        self.ans[self.root] += weight[u] * depth

        for v in tree[u]:
            if v == parent:
                continue
            self.dfs_sum(v, u, depth + 1)
            self.sub[u] += self.sub[v]

    def dfs_reroot(self, u: int, parent: int) -> None:
        """第二次 DFS：根从 u 换到儿子 v，v 子树内少走一步、其余多走一步。"""
        for v in tree[u]:
            if v == parent:
                continue
            self.ans[v] = self.ans[u] + self.total - 2 * self.sub[v]
            self.dfs_reroot(v, u)

最值型：求每个点的偏心距，答案里最小的那个点就是树的中心。

C++
cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

        #include <algorithm>
#include <vector>

const int maxn = 1e6 + 5;
using ll = long long;

// 全局邻接表：无向无权树，向 tree[u] 加边 tree[u].push_back(v) 和 tree[v].push_back(u)
using Graph = std::vector<int>;
Graph tree[maxn];

// 换根 DP（最值型）：求每个点到其它点的最远距离（偏心距）。
// 偏心距最小的点就是树的中心，所以这也是按换根求树的中心的办法。
// 用法：
// 1. 读入 n 与边；
// 2. TreeRerootMax solver(n);
// 3. const std::vector<ll>& ans = solver.solve(1);  // ans[u] 就是 u 的偏心距
struct TreeRerootMax {
    int n;
    int root;
    std::vector<ll> down;   // down[u]：u 子树内离 u 最远的距离
    std::vector<ll> up;     // up[u]：从 u 往父亲方向走能到的最远距离（不经过 u 的子树）
    std::vector<ll> ans;    // ans[u] = max(down[u], up[u])

    explicit TreeRerootMax(int n) : n(n), root(1), down(n + 1), up(n + 1), ans(n + 1) {}

    const std::vector<ll>& solve(int start = 1) {
        root = start;
        std::fill(down.begin(), down.end(), 0);
        std::fill(up.begin(), up.end(), 0);
        dfs_down(root, 0);
        dfs_up(root, 0);
        for (int u = 1; u <= n; u++) ans[u] = std::max(down[u], up[u]);
        return ans;
    }

    // 第一次 DFS：后序求 down[u]
    void dfs_down(int u, int parent) {
        down[u] = 0;
        for (int v : tree[u]) {
            if (v == parent) continue;
            dfs_down(v, u);
            if (down[v] + 1 > down[u]) down[u] = down[v] + 1;
        }
    }

    // 第二次 DFS：前序把"父亲方向"的信息传给儿子。
    // 对儿子 v 来说，向上的最远路 = 先走到 u，再从 u 选一条不经过 v 的最长路。
    // 所以要记 u 的子方向最长和次长，v 贡献了最长时改用次长。
    void dfs_up(int u, int parent) {
        ll best1 = -1;  // 子树方向最长的 down[儿子] + 1
        ll best2 = -1;  // 与 best1 来自不同儿子的次长

        for (int v : tree[u]) {
            if (v == parent) continue;
            ll candidate = down[v] + 1;
            if (candidate > best1) {
                best2 = best1;
                best1 = candidate;
            } else if (candidate > best2) {
                best2 = candidate;
            }
        }

        for (int v : tree[u]) {
            if (v == parent) continue;

            ll outside;  // 从 u 出发、不进入 v 子树能走的最远距离
            if (down[v] + 1 == best1) {
                outside = best2;  // v 提供了最长，只能改用次长
            } else {
                outside = best1;
            }
            if (up[u] > outside) outside = up[u];
            if (outside < 0) outside = 0;  // 实在没地方去，就停在 u

            up[v] = outside + 1;  // 从 v 先走到 u，再走 outside 步
        }

        for (int v : tree[u]) {
            if (v == parent) continue;
            dfs_up(v, u);
        }
    }
};
Python
python 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

        # 依赖模块级全局邻接表 tree：使用前先 tree = [[] for _ in range(n + 1)]，
# 再加无权边 tree[u].append(v) 和 tree[v].append(u)。节点编号 1..n。
# dfs 递归深度最坏 n（1e5+），使用前需 sys.setrecursionlimit(1 << 20)。

type Graph = list[list[int]]

tree: Graph = []


class TreeRerootMax:
    """换根 DP（最值型）：每个点到其它点的最远距离（偏心距），最小的点就是树的中心。"""

    n: int
    root: int
    down: list[int]
    up: list[int]
    ans: list[int]

    def __init__(self, n: int) -> None:
        self.n = n
        self.root = 1
        self.down = [0] * (n + 1)
        self.up = [0] * (n + 1)
        self.ans = [0] * (n + 1)

    def solve(self, start: int = 1) -> list[int]:
        """返回 ans 列表：ans[u] 就是 u 的偏心距。"""
        self.root = start
        self.down = [0] * (self.n + 1)
        self.up = [0] * (self.n + 1)
        self.dfs_down(self.root, 0)
        self.dfs_up(self.root, 0)

        for u in range(1, self.n + 1):
            self.ans[u] = max(self.down[u], self.up[u])
        return self.ans

    def dfs_down(self, u: int, parent: int) -> None:
        """第一次 DFS（后序）：down[u] 是 u 子树内离 u 最远的距离。"""
        self.down[u] = 0
        for v in tree[u]:
            if v == parent:
                continue
            self.dfs_down(v, u)
            if self.down[v] + 1 > self.down[u]:
                self.down[u] = self.down[v] + 1

    def dfs_up(self, u: int, parent: int) -> None:
        """第二次 DFS（前序）：算出每个儿子往上走的最远距离 up[v]。"""
        best1 = -1  # 子树方向最长距离
        best2 = -1  # 来自不同儿子的次长距离

        for v in tree[u]:
            if v == parent:
                continue
            candidate = self.down[v] + 1
            if candidate > best1:
                best2 = best1
                best1 = candidate
            elif candidate > best2:
                best2 = candidate

        for v in tree[u]:
            if v == parent:
                continue

            # 从 u 出发、不进入 v 子树的最远距离：v 提供最长时改用次长
            outside = best2 if self.down[v] + 1 == best1 else best1
            if self.up[u] > outside:
                outside = self.up[u]
            if outside < 0:
                outside = 0

            self.up[v] = outside + 1

        for v in tree[u]:
            if v == parent:
                continue
            self.dfs_up(v, u)

正确性

以求和型为例，归纳证明 ans⁡(v)\operatorname{ans}(v) 都算对。

  1. 根：第一次 DFS 把 ∑xwx⋅dep⁡(x)\sum_x w_x\cdot\operatorname{dep}(x) 全部加起来，ans⁡(1)\operatorname{ans}(1) 就是根的真实答案。
  2. 一步转移：设 ans⁡(u)\operatorname{ans}(u) 正确。把根从 uu 挪到儿子 vv，树上每个点到根的距离只会变 11：vv 子树内的点（共 S(v)S(v) 个）各减一，其余（W−S(v)W-S(v) 个）各加一，所以真实答案正好是 ans⁡(u)+W−2S(v)\operatorname{ans}(u)+W-2S(v)，与递推式一致。
  3. 沿路径归纳：第二次 DFS 从根出发按前序走，父亲先于儿子确定，于是任意点都能沿“根到它”的路径一步步推过去。

单向的推导已经够用了，反向看一眼也能佐证式子没写反：从 vv 挪回 uu，增量为 W−2S(u)=W−2(W−S(v))=2S(v)−WW-2S(u)=W-2(W-S(v))=2S(v)-W，正好抵消。

经典例题

1. luogu-P1364 题解

医院设置：每个点有居民数，选一个点使居民走的总路程最小。枚举 nn 个候选点各做一次 BFS 就能过（n≤100n\le 100），而换根写法是上面的求和型模板，O(n)O(n) 且顺便得到每个点的代价。

2. luogu-P1395 题解

会议：无权版的距离和最小。因为权重全为 11，最优位置就是树的重心，可以先求重心再一次 BFS；换根版则直接把所有点的距离和推出来取最小。

3. luogu-P3478 题解

STA-Station：求使“所有点深度之和”最大的根。增量仍是 n−2subtree_size⁡(v)n-2\operatorname{subtree\_size}(v)，只是最后取最大值而不是最小值——同一套骨架换一个比较方向。

4. luogu-P2986 题解

Great Cow Gathering：边带长度、点带奶牛数，求最小的“奶牛数 ×\times 距离和”。把增量的两侧规模换成“奶牛数”，距离变化换成“边权”，公式形状不变。

5. luogu-P3047 题解

Nearby Cows：计数型换根，增量靠容斥写出来，见上文第三类。

6. luogu-P5666 题解

CSP-S 2019 树的重心：枚举删掉的每条边、求两侧连通块的重心。单次换根不够，要把“沿最大部分走”和倍增、换根信息结合起来，属于这套骨架的进阶用法。

实践思考与扩展

  1. 先写暴力再换根。 换根公式写错时，输出往往是个“看起来合理”的大数。先用 O(n2)O(n^2) 的逐点 DFS 拿到正确答案，再和换根版对拍，能立刻发现增量写反、忘记次大值、边界没清空这类问题。
  2. 数值范围。 求和型的答案通常是“点权 ×\times 距离”的累加，10510^5 级的权值乘上 10510^5 级的距离就超过 int，一律用 64 位。
  3. 多解时的取舍。 重心、中心这类“只有一个最优值”的题目，直接用结论更短；一旦题目要“每个点的答案”或者加了点权、边权，换根 DP 的形态更稳。
  4. 递归深度。 链状数据下递归深度可达 nn。判题机通常给足栈空间；若目标环境栈很小，可以把两次 DFS 改成“先迭代求父亲与遍历序，再逆序/正序扫”，逻辑与递归版完全对应。

参考

相关练习题

  • 会议luogu / P1395普及换根 DP、树形 DP、树、树的重心
  • 医院设置luogu / P1364普及树、树形 DP、换根 DP、BFS、枚举、python
  • [POI 2008] STA-Stationluogu / P3478普及+/提高-树、树形 DP、换根 DP、链式前向星