树的重心

树的重心把删点后的最大连通块压到最小，可以用一次 DFS 统计子树大小在线性时间内求出。

  • 图论
  • 树
  • 树的重心
  • 树形 DP
前置知识

一句话算法

删掉一个点后，看剩下的最大连通块有多大；让这个最大块尽量小的点就是树的重心。

问题模型

给定一棵有 nn 个点的无权树。删除点 uu 以及与它相连的边后，原树会分成若干个连通块。

记这些连通块中的最大点数为 B(u)B(u)。我们要找使 B(u)B(u) 最小的点。

树的重心

树的重心就是使 B(u)B(u) 最小的点。

等价地，如果删除点 uu 后，每个连通块的大小都不超过 ⌊n/2⌋\lfloor n/2 \rfloor，那么 uu 是树的重心。

从子树大小得到判定式

重心的目标是点数平衡：删除这个点后，任何一边都不能超过一半。

任选点 root 作为根。设 sz[u] 表示以 u 为根的子树大小。

删除 u 后会产生两类连通块：

  1. 每个儿子 v 对应一块，大小是 sz[v]；
  2. u 的父亲方向对应一块，大小是 n - sz[u]。

因此：

B(u)=max⁡(n−subtree_size⁡[u],max⁡v 是 u 的儿子subtree_size⁡[v]) B(u)=\max\left(n-\operatorname{subtree\_size}[u], \max_{v\text{ 是 }u\text{ 的儿子}}\operatorname{subtree\_size}[v]\right)

判断 u 是不是重心，只需检查 B(u)B(u) 是否不超过 ⌊n/2⌋\lfloor n/2\rfloor。

只要一次 DFS 求出所有子树大小，就能顺便计算每个点的 B(u)B(u)。

不要漏掉父亲方向

sz[v] 只覆盖 u 的儿子方向。删除 u 后，父亲方向还有 n - sz[u] 个点，这是求重心时最常漏掉的一块。

算法步骤

  1. 任选一个点作为根，例如 1。
  2. DFS 进入点 u，令 sz[u] = 1。
  3. 递归处理每个儿子 v，把 sz[v] 加到 sz[u]。
  4. 用所有儿子子树大小和 n - sz[u] 计算 mx。
  5. 维护最小的 mx，记录所有取得最小值的点。

算法证明

  1. sz[u] 的正确性：叶子显然成立；递归返回后，u 的子树恰好由 u 自己与所有儿子的子树组成，归纳可得 sz[u] 就是 u 的子树大小。
  2. 判定没有遗漏：删除 u 后，连通块恰好是各儿子的子树和父亲方向，这些部分已经全部进入 B(u)B(u) 的公式。因此算法计算出的 mx 就是 B(u)B(u)，扫描所有点取最小值，必然得到全部重心。
  3. 两个定义等价：B(u)B(u) 最小当且仅当 B(u)⩽n/2B(u)\leqslant n/2。

    • 先证"最小 ⇒B(u)⩽n/2\Rightarrow B(u)\leqslant n/2"：反设最小点 uu 有 B(u)=m>n/2B(u)=m>n/2，即删除 uu 后有一块 CC 的大小为 m>n/2m>n/2。取 CC 中与 uu 相邻的点 vv：vv 朝 uu 一侧有 n−m<n/2n-m<n/2 个点，vv 的其他块都在 C∖{v}C\setminus\{v\} 内、每块都小于 mm，所以 B(v)<m=B(u)B(v)<m=B(u)，与 uu 是最小点矛盾。

      最小点 u 有一个超过 n/2 的块 C，移入 C 中相邻的点 v 后 B(v) 小于 m，与最小性矛盾

    • 再证"B(u)⩽n/2⇒B(u)\leqslant n/2\Rightarrow 最小"：反设存在 vv 使 B(v)<B(u)⩽n/2B(v)<B(u)\leqslant n/2，则 B(v)<n/2B(v)<n/2。

      取路径 u=p0,p1,…,pk=vu=p_0,p_1,\ldots,p_k=v。对路径上的每条边 (pi,pi+1)(p_i,p_{i+1})，删掉它后树分成两块，记含 vv 的那块的大小为 fif_i（i=0,…,k−1i=0,\ldots,k-1）。观察 ff 的三个性质：

      1. f0⩽n/2f_0\leqslant n/2：删掉 (u,p1)(u,p_1) 后含 vv 的块，恰好也是删掉 uu 后含 vv 的块，它是删 uu 后的一块，大小 ⩽B(u)⩽n/2\leqslant B(u)\leqslant n/2。
      2. fk−1>n/2f_{k-1}>n/2：删掉 (pk−1,v)(p_{k-1},v) 后含 vv 的块 == 整棵树 −- 含 uu 的那块。含 uu 的那块是删 vv 后的一块，大小 ⩽B(v)<n/2\leqslant B(v)<n/2，故 fk−1=n−f_{k-1}=n-（含 uu 的块）⩾n−B(v)>n/2\geqslant n-B(v)>n/2。
      3. ff 严格递减：fi+1f_{i+1} 对应的块 == fif_i 对应的块 −- pi+1p_{i+1} 自己 −-（pi+1p_{i+1} 挂在路径外的分支），所以 fi+1⩽fi−1f_{i+1}\leqslant f_i-1。

      但性质 3 给出 f0>fk−1f_0>f_{k-1}，与性质 1、2 的 f0⩽n/2<fk−1f_0\leqslant n/2<f_{k-1} 矛盾。

      沿 u 到 v 的路径，含 v 的连通块 f0、f1 直到 f(k-1) 逐层严格包含，但两端大小关系相互矛盾

复杂度分析

  • 时间复杂度：O(n)O(n)。每个点和每条边只处理常数次。
  • 空间复杂度：O(n)O(n)。邻接表、子树大小和递归栈都占线性空间。

代码模板

模板返回全部重心，并按编号升序排列。best 是删除重心后最大连通块的大小。

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

        #include <algorithm>
#include <vector>

using Graph = std::vector<std::vector<int>>;
Graph tree;  // 全局邻接表：使用前先 resize(n+1) 并加边

// 如何使用：
// 1. tree.resize(n + 1)，读入边：tree[u].push_back(v); tree[v].push_back(u);
// 2. TreeCentroid tc(n);
// 3. vector<int> cs = tc.find_centroids();  // 返回所有重心，编号升序

// 求树的所有重心。
// 重心：删除该点后，剩下的每个连通块大小都不超过 n/2。
struct TreeCentroid {
    int n;
    std::vector<int> sz;   // sz[u] = u 的子树大小
    std::vector<int> ans;  // 答案：所有重心，按编号升序
    int best;              // 最小的 B(u)：删除 u 后最大的连通块大小

    explicit TreeCentroid(int n) : n(n), best(n), sz(n + 1) {}

    // 返回所有重心（编号升序）
    std::vector<int> find_centroids(int root = 1) {
        best = n;
        ans.clear();
        dfs(root, 0);
        std::sort(ans.begin(), ans.end());
        return ans;
    }

    // 统计子树大小，同时计算每个点的 B(u) = 删除 u 后最大的连通块大小
    void dfs(int u, int parent) {
        // 如果邻接表不叫 tree，把循环里的 tree 替换成你的变量名
        sz[u] = 1;
        int mx = 0;  // B(u)：先看各儿子子树

        for (int v : tree[u]) {
            if (v == parent) continue;
            dfs(v, u);
            sz[u] += sz[v];
            mx = std::max(mx, sz[v]);
        }

        // 父亲方向也是一块：整棵树减去 u 的子树
        mx = std::max(mx, n - sz[u]);

        // 记录 B(u) 最小的点（可能不止一个）
        if (mx < best) {
            best = mx;
            ans = {u};
        } else if (mx == best) {
            ans.push_back(u);
        }
    }
};

另一种写法：不维护全局最小值，直接用等价判定 B(u) ≤ n/2 收集重心，代码更短。

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

        #include <algorithm>
#include <vector>

using Graph = std::vector<std::vector<int>>;
Graph tree;  // 全局邻接表：使用前先 resize(n+1) 并加边

// 如何使用：
// 1. tree.resize(n + 1)，读入边：tree[u].push_back(v); tree[v].push_back(u);
// 2. TreeCentroid2 tc(n);
// 3. vector<int> cs = tc.find_centroids();  // 返回所有重心，编号升序

// 求树的所有重心。
// 重心：删除该点后，剩下的每个连通块大小都不超过 n/2。
// 与 tree_centroid.cpp 不同：不维护全局最小值，直接按"最大连通块 ≤ n/2"判定重心。
struct TreeCentroid2 {
    int n;
    std::vector<int> sz;   // sz[u] = u 的子树大小
    std::vector<int> ans;  // 答案：所有重心，按编号升序

    explicit TreeCentroid2(int n) : n(n), sz(n + 1) {}

    // 返回所有重心（编号升序）
    std::vector<int> find_centroids(int root = 1) {
        ans.clear();
        dfs(root, 0);
        std::sort(ans.begin(), ans.end());
        return ans;
    }

    // 统计子树大小；若 B(u) = 删除 u 后最大的连通块大小 ≤ n/2，u 就是重心
    void dfs(int u, int parent) {
        // 如果邻接表不叫 tree，把循环里的 tree 替换成你的变量名
        sz[u] = 1;
        int mx = 0;  // B(u)：先看各儿子子树

        for (int v : tree[u]) {
            if (v == parent) continue;
            dfs(v, u);
            sz[u] += sz[v];
            mx = std::max(mx, sz[v]);
        }

        // 父亲方向也是一块：整棵树减去 u 的子树
        mx = std::max(mx, n - sz[u]);

        // 等价判定：B(u) ≤ n/2 ⟺ u 是重心
        if (mx <= n / 2) ans.push_back(u);
    }
};

代码实现

输入一棵无权树，第一行输出重心个数，第二行按编号升序输出所有重心。

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

        #include <bits/stdc++.h>
using namespace std;

using Graph = vector<vector<int>>;
Graph tree;  // 全局邻接表：使用前先 resize(n+1) 并加边

// 求树的所有重心。
// 重心：删除该点后，剩下的每个连通块大小都不超过 n/2。
struct TreeCentroid {
    int n;
    vector<int> sz;   // sz[u] = u 的子树大小
    vector<int> ans;  // 答案：所有重心，按编号升序
    int best;         // 最小的 B(u)：删除 u 后最大的连通块大小

    explicit TreeCentroid(int n) : n(n), best(n), sz(n + 1) {}

    // 返回所有重心（编号升序）
    vector<int> find_centroids(int root = 1) {
        best = n;
        ans.clear();
        dfs(root, 0);
        sort(ans.begin(), ans.end());
        return ans;
    }

    // 统计子树大小，同时计算每个点的 B(u) = 删除 u 后最大的连通块大小
    void dfs(int u, int parent) {
        sz[u] = 1;
        int mx = 0;  // B(u)：先看各儿子子树

        for (int v : tree[u]) {
            if (v == parent) continue;
            dfs(v, u);
            sz[u] += sz[v];
            mx = max(mx, sz[v]);
        }

        // 父亲方向也是一块：整棵树减去 u 的子树
        mx = max(mx, n - sz[u]);

        // 记录 B(u) 最小的点（可能不止一个）
        if (mx < best) {
            best = mx;
            ans = {u};
        } else if (mx == best) {
            ans.push_back(u);
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    tree.resize(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    TreeCentroid tc(n);
    vector<int> answer = tc.find_centroids();
    cout << answer.size() << '\n';
    for (size_t i = 0; i < answer.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << answer[i];
    }
    cout << '\n';
    return 0;
}

测试用例

两个重心

输入：

8
1 2
1 3
2 4
2 5
3 6
6 7
6 8

输出：

2
1 3

删除 1 后，最大的部分是 {3,6,7,8}；删除 3 后，最大的部分是 {1,2,4,5}。两块大小都是 4=n/24=n/2，所以 1 和 3 都是重心。

        1
       / \
      2   3
     / \   \
    4   5   6
           / \
          7   8

单点树

输入：

1

输出：

1
1

重要性质

1. 树的重心不是树的中心

这两个名字接近，但优化目标不同。

概念 优化目标 常用求法
树的重心 删除该点后的最大连通块最小 子树大小
树的中心 到其他点的最大距离最小 直径中点

例如，一条长链的一端挂着许多叶子时，中心更在意最远距离，重心更在意两边各有多少个点，它们可能不是同一个点。

2. 重心一定存在

站在任意点 u 上，假设删除 u 后有一块包含了超过一半的点，那么树明显向这一块“偏重”，重心一定在这个方向。

删除 u 后：

删除 u 后，左右两块分别是 2 个点和 6 个点，超过 n/2 的一侧就是重心所在方向

右侧超过 n/2n/2，重心一定在右侧；向右移动继续判断。

于是得到一种寻找重心的过程：

  1. 如果删除 u 后没有连通块超过 n/2n/2，那么 u 已经是重心。
  2. 否则，超过 n/2n/2 的连通块至多有一个，向这一块的相邻点 v 移动。
  3. 移到 v 后，回到 u 的那一块大小小于 n/2n/2，所以不会立刻走回去。

树没有环，因此这个移动过程不可能绕圈，最终一定停下。停下时所有连通块都不超过 n/2n/2，所以停点就是重心，重心一定存在。

3. 至多有两个重心

设 c 是一个重心。

  • 如果删除 c 后每一块都严格小于 n/2n/2，那么其他点所在方向的总点数不足一半；移动到任何其他点，包含 c 的反方向都会超过一半，所以重心唯一。
  • 如果某一块恰好有 n/2n/2 个点，设这块中与 c 相邻的点为 v。删除 v 后，c 方向也恰好有 n/2n/2 个点，其他块更小，所以 v 也是重心。

第二种情况只会产生相邻的 c、v 两个重心。因此树至少有一个重心，至多有两个重心；如果有两个，它们一定相邻。

4. 重心使距离和最小

在无权树上，重心也使到所有点的距离和最小。

设边 (u, v) 切开后，v 一侧有 ss 个点。位置从 u 移到 v：

  • 这 ss 个点的距离各减少 11；
  • 其余 n−sn-s 个点的距离各增加 11。

所以距离和的变化为：

F(v)−F(u)=(n−s)−s=n−2s F(v)-F(u)=(n-s)-s=n-2s

当 s>n/2s>n/2 时，向 v 移动会让距离和变小；没有任何方向超过一半时，距离和已经最小。这正是重心的判定条件。

从 u 移到 v 时，v 侧 s 个点距离减一，其余 n-s 个点距离加一

5. 重心分治中的作用

重心分治每次选当前连通块的重心作为分治点。删除它后，每个子问题的规模至多是原来的一半，因此递归层数是 O(log⁡n)O(\log n)。

“求树的重心”是重心分治的基础步骤，但它本身还不是完整的重心分治算法。

应用分类详解

树的重心本质上是在树上找一个最平衡的切分点。

一、直接寻找平衡根

典型模式： 选择一个点作为根或枢纽，希望删掉它后最大的剩余部分尽量小。

识别信号： 题面出现“删除一个点”“最大连通块最小”“每部分不超过一半”。

核心建模： 用子树大小表示儿子方向，用 n - sz[u] 表示父亲方向。

二、最小化全树距离和

典型模式： 在无权树上选会场，使所有点到会场的距离和最小。

识别信号： 出现“所有点到选址点的距离总和最小”。

核心建模： 跨过一条边时，距离和变化由两侧点数之差决定；最优点满足每侧都不超过一半。

三、递归拆分树上问题

典型模式： 需要反复统计经过某个分治点的路径，再递归处理剩余连通块。

识别信号： 树上点对、路径长度统计，且普通 DFS 会重复处理大量跨子树路径。

核心建模： 每次取重心，保证子问题规模至少减半，从而把递归深度控制在 O(log⁡n)O(\log n)。

四、删边后的重心变化

典型模式： 删除每条边后，分别询问两侧连通块的重心。

识别信号： 对很多棵只差一条边或一个根的树重复求重心。

核心建模： 不能每次重新 DFS，需要利用最大子树方向、换根或倍增复用原树信息。

应用场景 维护的信息 典型复杂度
单次求重心 子树大小、最大剩余块 O(n)O(n)
距离和选址 子树大小、距离和 O(n)O(n)
重心分治 当前连通块大小、删除标记 常见为 O(nlog⁡n)O(n\log n)
多次删边求重心 最大子树方向、换根或倍增信息 依题目设计

经典例题

1. 树的重心模板

给出一棵树，输出所有重心。重点是同时检查儿子方向和父亲方向，并正确处理双重心。

2. luogu-P1395 题解

要求选择会议地点，使所有点到会场的距离和最小。重心性质可以确定最优位置；如果还要得到最小距离和，可以配合换根 DP 在线性时间内计算。

3. luogu-P5666 题解

枚举删除每条边后两侧连通块的全部重心。每次重新 DFS 会达到 O(n2)O(n^2)，需要把“沿最大部分寻找重心”的性质与换根、倍增结合起来。

实践思考与扩展

  1. 如果每个点带有权值，把“点数”换成“点权和”，可以定义树的带权重心。
  2. 如果只要求任意一个重心，可以从任意点不断走向超过一半的连通块。
  3. 递归 DFS 在退化成链的树上可能达到 O(n)O(n) 层；栈空间严格受限时，可以改用显式栈求父亲和遍历序，再逆序累加子树大小。

参考