[CSP-S 2019] 树的重心

GitHub跳转原题关系图 Canvas 关系图返回列表

对每条边断开后，利用最大子树方向唯一的性质沿 heavy 链倍增定位两侧重心，配合换根在 O(log n) 内枚举每条边。

OJ: luogu

题目 ID: P5666

难度:省选/NOI-

标签:重心换根倍增树形结构

日期: 2026-07-16 23:59

形式化题目

给定一棵 $n$ 个节点的树。对每条边 $(u,v)$ ，删掉它后树分成两个连通块，分别求出两个连通块的所有重心的编号之和（一个大小为 $m$ 的树最多有两个重心，此时两个都要计入）。对 $n-1$ 条边的贡献求和，输出总和。

这张图是样例第一组数据的树：

text

以切边 $(1,2)$ 为例：删掉它后得到 $\{1\}$ 与 $\{2,3,4,5\}$ 两个连通块，重心分别是 $\{1\}$ 与 $\{2,3\}$ （两个重心相邻、各侧恰好一半）。观察这个例子：重心判定只看"删掉该点后最大连通部分 $\leqslant \lfloor m/2 \rfloor$ "，而样例解释也印证了"重心可能有两个"时编号都要累加。

思路

先看一个可以直接验证想法的朴素解：

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:34
 * update_at: 2026-08-12 22:48
 */
// brute.cpp：小数据暴力解。对每条边断开，两侧连通块分别以断边端点为根，
// 用“沿最大子树方向下降”在 O(size) 内找重心并累加编号和。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n;
vector<int> g[MAXN];            // 邻接表存树
int edge_u[MAXN], edge_v[MAXN]; // 按输入顺序存每条边
bool in_comp[MAXN];             // 标记当前连通块内的节点
int fa[MAXN], sz[MAXN];         // 连通块内以根做 DFS 得到的父节点与子树大小

// 收集从 start 出发、不经过断边 (ban_u, ban_v) 的连通块。
void collect_component(int start, int ban_u, int ban_v) {
    memset(in_comp, 0, sizeof(in_comp));
    queue<int> q;
    q.push(start);
    in_comp[start] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if ((u == ban_u && v == ban_v) || (u == ban_v && v == ban_u)) {
                continue;
            }
            if (!in_comp[v]) {
                in_comp[v] = true;
                q.push(v);
            }
        }
    }
}

// 在当前连通块内以 root 为根做 DFS，求出 sz[] 与 fa[]。
void dfs_size(int root) {
    sz[root] = 1;
    for (int i = 0; i < (int)g[root].size(); i++) {
        int v = g[root][i];
        if (v == fa[root] || !in_comp[v]) {
            continue;
        }
        fa[v] = root;
        dfs_size(v);
        sz[root] += sz[v];
    }
}

// 求以 root 为根的连通块的重心编号和（沿最大子树方向下降，O(size)）。
int centroid_sum(int root) {
    int total = sz[root];
    int cur = root;
    int max_child = 0;

    // 不断进入“大小超过一半”的唯一子树方向；超过一半的子树至多一个，
    // 所以方向唯一，走到停就是重心。
    while (true) {
        max_child = 0;
        for (int i = 0; i < (int)g[cur].size(); i++) {
            int v = g[cur][i];
            if (in_comp[v] && fa[v] == cur && sz[v] > sz[max_child]) {
                max_child = v;
            }
        }
        if (max_child != 0 && sz[max_child] * 2 > total) {
            cur = max_child;
        } else {
            break;
        }
    }

    // cur 是重心；若最大子树恰好为一半，其根与 cur 是两个相邻重心，编号都要计入。
    int result = cur;
    if (max_child != 0 && sz[max_child] * 2 == total) {
        result += max_child;
    }
    return result;
}

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

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            g[i].clear();
        }
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            edge_u[i] = u;
            edge_v[i] = v;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        long long answer = 0;
        for (int i = 1; i < n; i++) {
            int u = edge_u[i], v = edge_v[i];
            // u 一侧：以 u 为根的连通块。
            collect_component(u, u, v);
            fa[u] = 0;
            dfs_size(u);
            answer += centroid_sum(u);
            // v 一侧：以 v 为根的连通块。
            collect_component(v, u, v);
            fa[v] = 0;
            dfs_size(v);
            answer += centroid_sum(v);
        }
        cout << answer << '\n';
    }

    return 0;
}

brute.cpp 对每条边断开后，在两侧连通块内分别以断边端点为根做 DFS 求子树大小，然后沿"最大子树方向"一步步下降找重心：只要最大儿子的子树大小 $> m/2$ 就进入它，停下的点就是重心；若最大儿子恰好 $m/2$ ，它和停点都是重心。正确，但每条边都要重新 DFS 且下降 $O(\text{高度})$ 步，总 $O(n^2)$ 。

关键观察有三条：

方向唯一：以连通块内任一点为根，若某儿子子树大小 $> m/2$ ，这样的儿子至多一个（两个儿子大小之和 $\leqslant m-1$ ），且重心一定在该方向内，所以"沿最大子树方向下降"是一条确定的路线。
下降可以倍增：以整棵树 1 号点为根预处理每个点的最大子节点（heavy 方向），沿 heavy 链的大小严格递减，"子树大小 $\geqslant m/2$ "在链上单调，因此可以用跳表 $jump[u][k]$ （沿 heavy 链跳 $2^k$ 步）大步到小步贪心下降， $O(\log n)$ 找到重心；若终点恰好 $sz[u] \cdot 2 = m$ ，则 $fa[u]$ 是第二个重心。
换根只改一个点：断开边 $(u,v)$ 并把 $v$ 临时当根， $v$ 一侧就是子树 $v$ （内部完全不变）； $u$ 一侧是"补树"，只有 $u$ 的儿子集合少了 $v$ ，所以只需把 $u$ 的 heavy 方向换成"除 $v$ 外最大的邻居"、改 $sz[u]$ 、 $sz[v]$ 、 $fa$ 即可，其余节点零修改。

以下面的小图看第 3 条：切边 $(1,2)$ 后把 $2$ 临时当根， $2$ 侧是子树 $\{2,3,4,5\}$ 直接求重心； $1$ 侧补树只有 $\{1\}$ ：

text

1
2
3
4
5
6切边 (1,2)，把 2 临时当根：
  2 侧 = 子树 {2,3,4,5}   m=4，sz[3]=2, sz[4]=1
  下降：2 --(2*sz[3]=4 ≥ 4)--> 3 --(2*sz[5]=2 < 4 停)
  重心 3，且 2*sz[3]==4，父节点 2 也是重心 -> {2,3}（与样例解释一致）

  1 侧 = 补树 {1}        m=1，重心 1

于是算法：第一遍以 1 为根 BFS 求 $fa/sz/heavy$ 并按层构建跳表；第二遍用显式栈做换根 DFS 枚举每条边——进入边 $(u,v)$ 时先求子树 $v$ 的重心和，临时把根换成 $v$ 后求补树（根 $u$ ）的重心和，递归进入 $v$ ，返回时恢复现场。每步 $O(\log n)$ 。

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:34
 * update_at: 2026-08-12 22:48
 */
// main.cpp：对每条边断开，用“沿最大子树方向倍增”求两侧连通块的重心编号和。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
const int LOGN = 20; // 2^19 > 3e5，跳表需要 0..19 共 20 层

int n;
vector<int> g[MAXN];          // 邻接表存树
int sz[MAXN];                 // 当前定向下以 i 为根的子树大小（定向根的大小为 n）
int fa[MAXN];                 // 当前定向下 i 的父节点
int heavy_son[MAXN];          // 初始定向下 i 的最大子节点
int jump_table[MAXN][LOGN];   // jump_table[i][k]：沿 heavy 链向下跳 2^k 步到达的点
long long answer;             // 所有边断开后两侧重心编号和的总和

// 重新构建节点 u 的倍增表。换根只会改变 u 一层的 heavy 方向，其余节点不变。
void rebuild_jump(int u) {
    for (int k = 1; k < LOGN; k++) {
        jump_table[u][k] = jump_table[jump_table[u][k - 1]][k - 1];
    }
}

// 求“以 root 为根、大小为 sz[root] 的连通块”的重心编号和（重心可能有 1 或 2 个）。
// 从 root 出发沿最大子树方向下降，走到最后一个满足“子树不小于一半”的节点；
// 若最大子树恰好为一半，说明它和父节点是两个重心，两个编号都要计入。
void add_centroid_sum(int root) {
    int total = sz[root];
    int u = root;

    // 倍增贪心：大步到小步，能跳就跳（子树大小不小于 half）。
    for (int k = LOGN - 1; k >= 0; k--) {
        int v = jump_table[u][k];
        if (v != 0 && sz[v] * 2 >= total) {
            u = v;
        }
    }

    answer += u;
    if (sz[u] * 2 == total) {
        answer += fa[u];
    }
}

// 求节点 u 在当前定向下最大、次大的相邻组件大小对应的邻居。
// first/second 用于换根时把 v 排除后重选 u 的最大子树方向。
void largest_two(int u, int& first, int& second) {
    first = second = 0;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (sz[v] >= sz[first]) {
            second = first;
            first = v;
        } else if (sz[v] >= sz[second]) {
            second = v;
        }
    }
}

// 换根 DFS 的显式栈帧：node 的邻居已处理到 stack_idx[top]，
// stack_first/stack_second 是进入该帧时算好的最大、次大相邻组件。
int stack_node[MAXN], stack_father[MAXN], stack_idx[MAXN];
int stack_first[MAXN], stack_second[MAXN];

// 帧弹出时恢复的现场（由父帧在压入时保存）：
// changed_node 与 changed_child 是换根时被修改的边两端点。
int restore_fa_node[MAXN], restore_fa_child[MAXN];
int restore_sz_node[MAXN], restore_sz_child[MAXN];
int restore_jump0[MAXN], restore_changed_node[MAXN], restore_changed_child[MAXN];

// 第一遍 BFS 的顺序与队列（迭代写法避免 3e5 深度递归爆栈）。
int order_arr[MAXN], order_cnt;
int bfs_queue[MAXN];

void solve_one() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        sz[i] = 1;
        fa[i] = 0;
        heavy_son[i] = 0;
        for (int k = 0; k < LOGN; k++) {
            jump_table[i][k] = 0;
        }
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 第一遍：以 1 为根做 BFS，得到 fa[] 与遍历顺序 order_arr[]。
    order_cnt = 0;
    int head_q = 0, tail_q = 0;
    fa[1] = 0;
    bfs_queue[tail_q++] = 1;
    while (head_q < tail_q) {
        int u = bfs_queue[head_q++];
        order_arr[order_cnt++] = u;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == fa[u]) {
                continue;
            }
            fa[v] = u;
            bfs_queue[tail_q++] = v;
        }
    }

    // 逆序遍历求 sz[] 与 heavy_son[]（保证子节点的信息先算好）。
    sz[0] = 0;
    for (int i = n - 1; i >= 1; i--) { // order_arr[0] 是根 1，跳过
        int u = order_arr[i];
        int p = fa[u];
        sz[p] += sz[u];
        if (sz[u] > sz[heavy_son[p]]) {
            heavy_son[p] = u;
        }
    }

    // 构建初始倍增表：jump_table[u][0] 就是 heavy 方向。
    // 必须按层构建：第 k 层只依赖第 k-1 层，保证任意节点的下层都已完成。
    for (int u = 1; u <= n; u++) {
        jump_table[u][0] = heavy_son[u];
    }
    for (int k = 1; k < LOGN; k++) {
        for (int u = 1; u <= n; u++) {
            jump_table[u][k] = jump_table[jump_table[u][k - 1]][k - 1];
        }
    }

    // 第二遍：显式栈模拟换根 DFS，枚举每条边并统计两侧重心。
    answer = 0;
    int top = 1;
    stack_node[1] = 1;
    stack_father[1] = 0;
    stack_idx[1] = 0;
    largest_two(1, stack_first[1], stack_second[1]);

    while (top >= 1) {
        int node = stack_node[top];
        int father = stack_father[top];

        if (stack_idx[top] == (int)g[node].size()) {
            // 本帧处理完毕：弹出并恢复父帧换根时保存的现场（根帧无需恢复）。
            if (top >= 2) {
                int cn = restore_changed_node[top];
                int cc = restore_changed_child[top];
                fa[cn] = restore_fa_node[top];
                fa[cc] = restore_fa_child[top];
                sz[cn] = restore_sz_node[top];
                sz[cc] = restore_sz_child[top];
                jump_table[cn][0] = restore_jump0[top];
                rebuild_jump(cn);
            }
            top--;
            continue;
        }

        int v = g[node][stack_idx[top]];
        stack_idx[top]++;
        if (v == father) {
            continue;
        }

        // 边 (node, v) 断开后，v 一侧就是当前定向下 v 的子树，直接求重心。
        add_centroid_sum(v);

        // 保存现场，准备把 v 临时变成定向根。
        restore_fa_node[top + 1] = fa[node];
        restore_fa_child[top + 1] = fa[v];
        restore_sz_node[top + 1] = sz[node];
        restore_sz_child[top + 1] = sz[v];
        restore_jump0[top + 1] = jump_table[node][0];
        restore_changed_node[top + 1] = node;
        restore_changed_child[top + 1] = v;

        // 换根：node 的 heavy 方向变成“除 v 外最大的相邻组件”。
        jump_table[node][0] = (v == stack_first[top]) ? stack_second[top] : stack_first[top];
        rebuild_jump(node);
        sz[node] -= sz[v];
        sz[v] += sz[node];

        // node 一侧是“补树”（整棵树去掉 v 的子树），求重心。
        add_centroid_sum(node);

        // 更新父指针，进入 v 的子树继续枚举。
        fa[node] = v;
        fa[v] = father;

        top++;
        stack_node[top] = v;
        stack_father[top] = node;
        stack_idx[top] = 0;
        largest_two(v, stack_first[top], stack_second[top]);
    }

    cout << answer << '\n';
}

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

    int T;
    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

复杂度

时间：预处理 $O(n \log n)$ （跳表按层构建）；每条边两次重心查询 + 一次跳表重建 $O(\log n)$ ，总 $O(n \log n)$ 。
空间：跳表 $O(n \log n)$ ，其余数组 $O(n)$ 。

总结

本题的骨架是"重心判定只看最大部分，沿最大部分方向下降"这一性质：它让求重心变成沿一条链走，而链上大小单调又让它能吃下倍增跳跃的加速；换根之所以可行，是因为切边后只有一个端点需要改信息。rbook 的《倍增跳跃》讲了"大步到小步试探、能跳就跳"的跳表原理，正是本题 $O(\log n)$ 求重心所依赖的模型；jump[u][k] 沿 heavy 链下降的写法与倍增 LCA 的跳表同理，只是方向相反。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21朴素做法（brute.cpp）
  枚举每条边断开，两侧连通块各自以断边端点为根
  沿“最大子树方向”一步步下降找重心        O(n^2) 每棵树
        |
        | 瓶颈：每边重新 DFS + 下降 O(高度) 步
        v
关键观察
  1) 重心 ⇔ 最大连通部分 <= m/2
  2) 若某子树 > m/2，该方向唯一，重心必在其中
  3) 双重心只在“恰好一半”出现，两个都要加
        |
        v
两个加速（main.cpp）
  A. heavy 链倍增：jump[u][k] = 沿最大子树方向跳 2^k 步
     “子树大小 >= m/2”沿链单调，贪心下降 O(log n) 找到重心
  B. 换根枚举每条边：断开 (u,v) 后把 v 临时当根
     v 侧 = 子树 v，u 侧 = 补树；只有 u 的 heavy 方向
     与 sz[u]、sz[v]、fa 需要改，其余节点零修改
        |
        v
每边 O(log n)，总 O(n log n)，空间 O(n log n)

图中从上到下对应"暴力慢在哪"“重心下降方向为什么唯一”“倍增 + 换根如何复用信息”。核心是：把"找重心"从逐点判定压缩成"沿唯一方向走"，再让"沿唯一方向走"和"切边后的补树"都能在 $O(\log n)$ 内完成。

P5666 [CSP-S 2019] 树的重心

题目描述

小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：

一个大小为 $n$ 的树由 $n$ 个结点与 $n - 1$ 条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。
对于一个大小为 $n$ 的树与任意一个树中结点 $c$ ，称 $c$ 是该树的重心当且仅当在树中删去 $c$ 及与它关联的边后，分裂出的所有子树的大小均不超过 $\lfloor \frac{n}{2} \rfloor$ （其中 $\lfloor x \rfloor$ 是下取整函数）。对于包含至少一个结点的树，它的重心只可能有 1 或 2 个。

课后老师给出了一个大小为 $n$ 的树 $S$ ，树中结点从 $1 \sim n$ 编号。小简单的课后作业是求出 $S$ 单独删去每条边后，分裂出的两个子树的重心编号和之和。即：

\sum_{(u,v) \in E} \left( \sum_{1 \leq x \leq n \atop 且 x 号点是 S'_u 的重心} x + \sum_{1 \leq y \leq n \atop 且 y 号点是 S'_v 的重心} y \right)

上式中， $E$ 表示树 $S$ 的边集， $(u,v)$ 表示一条连接 $u$ 号点和 $v$ 号点的边。 $S'_u$ 与 $S'_v$ 分别表示树 $S$ 删去边 $(u,v)$ 后， $u$ 号点与 $v$ 号点所在的被分裂出的子树。

小简单觉得作业并不简单，只好向你求助，请你教教他。

输入格式

本题包含多组测试数据。

第一行一个整数 $T$ 表示数据组数。

接下来依次给出每组输入数据，对于每组数据：

第一行一个整数 $n$ 表示树 $S$ 的大小。

接下来 $n − 1$ 行，每行两个以空格分隔的整数 $u_i$ ， $v_i$ ，表示树中的一条边 $(u_i,v_i)$ 。

输出格式

共 $T$ 行，每行一个整数，第 $i$ 行的整数表示：第 $i$ 组数据给出的树单独删去每条边后，分裂出的两个子树的重心编号和之和。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
232
56

说明/提示

【样例 1 解释】

对于第一组数据：

删去边 $(1,2)$ ，1 号点所在子树重心编号为 $\{1\}$ ，2 号点所在子树重心编号为 $\{2,3\}$ 。

删去边 $(2,3)$ ，2 号点所在子树重心编号为 $\{2\}$ ，3 号点所在子树重心编号为 $\{3,5\}$ 。

删去边 $(2,4)$ ，2 号点所在子树重心编号为 $\{2,3\}$ ，4 号点所在子树重心编号为 $\{4\}$ 。

删去边 $(3,5)$ ，3 号点所在子树重心编号为 $\{2\}$ ，5 号点所在子树重心编号为 $\{5\}$ 。

因此答案为 $1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32$ 。

【数据范围】

测试点编号	$n =$	特殊性质
$1 \sim 2$	$7$	无
$3 \sim 5$	$199$	无
$6 \sim 8$	$1999$	无
$9 \sim 11$	$49991$	A
$12 \sim 15$	$262143$	B
$16$	$99995$	无
$17 \sim 18$	$199995$	无
$19 \sim 20$	$299995$	无

表中特殊性质一栏，两个变量的含义为存在一个 $1 \sim n$ 的排列 $p_i (1 \leq i \leq n)$ ，使得：

A：树的形态是一条链。即 $\forall 1 \leq i \lt n$ ，存在一条边 $(p_i, p_{i + 1})$ 。
B：树的形态是一个完美二叉树。即 $\forall 1 \leq i \leq \frac{n-1}{2}$ ，存在两条边 $(p_i, p_{2i})$ 与 $(p_i, p_{2i+1})$ 。

对于所有测试点： $1 \leq T \leq 5 , 1 \leq u_i,v_i \leq n$ 。保证给出的图是一个树。

[CSP-S 2019] 树的重心

目录

形式化题目

思路

代码

复杂度

总结

图示解析