[CSP-S 2019] 树的重心

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

换根维护最大相邻组件，并沿最大子树链快速定位每个分割树的重心。

OJ: luogu

题目 ID: P5666

难度:省选/提高

标签:重心换根倍增python

日期: 2026-07-17 02:00

题意

删除原树每条边，分别求两个连通块的重心编号和，最后求总和。

思路

一个连通块的重心沿“最大相邻组件”方向向下走，直到下一步子树不足半数。预处理每个节点的最大子树链及其倍增跳表；换根遍历一条边时临时交换两侧的父子关系和子树大小，分别定位两侧重心后恢复现场。

Python 知识

array("i") 保存多层跳表和子树大小。
用显式栈保存待恢复状态，模拟递归换根，避免 30 万深度的 Python 调用栈。
rebuild 只更新发生换根的节点，减少跳表维护开销。

代码

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104import sys
from array import array


input = sys.stdin.buffer.readline
test_cases = int(input())
answers = []
for _ in range(test_cases):
    n = int(input())
    graph = [[] for _ in range(n + 1)]
    for __ in range(n - 1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    parent = array("i", [0]) * (n + 1)
    order = array("i", [1])
    for node in order:
        for neighbor in graph[node]:
            if neighbor != parent[node]:
                parent[neighbor] = node
                order.append(neighbor)
    subtree = array("i", [1]) * (n + 1)
    subtree[0] = 0
    heavy = array("i", [0]) * (n + 1)
    for node in reversed(order[1:]):
        subtree[parent[node]] += subtree[node]
        if subtree[node] > subtree[heavy[parent[node]]]:
            heavy[parent[node]] = node

    log = n.bit_length()
    jump = [array("i", [0]) * (n + 1) for _ in range(log)]
    for node in range(1, n + 1):
        jump[0][node] = heavy[node]
    for level in range(1, log):
        previous, current = jump[level - 1], jump[level]
        for node in range(1, n + 1):
            current[node] = previous[previous[node]]

    def rebuild(node):
        for level in range(1, log):
            jump[level][node] = jump[level - 1][jump[level - 1][node]]

    def centroid_sum(root):
        total = subtree[root]
        node = root
        for level in range(log - 1, -1, -1):
            candidate = jump[level][node]
            if candidate and subtree[candidate] * 2 >= total:
                node = candidate
        value = node
        if subtree[node] * 2 == total:
            value += parent[node]
        return value

    answer = 0
    # A frame stores the next adjacency position and the two largest current
    # neighbour components. Mutations are rolled back after returning.
    def largest_two(node):
        first = second = 0
        for neighbor in graph[node]:
            if subtree[neighbor] >= subtree[first]:
                second, first = first, neighbor
            elif subtree[neighbor] > subtree[second]:
                second = neighbor
        return first, second

    first, second = largest_two(1)
    stack = [[1, 0, 0, first, second, None]]
    while stack:
        frame = stack[-1]
        node, father, index, first, second, restore = frame
        if index == len(graph[node]):
            stack.pop()
            if restore is not None:
                (old_parent_node, old_parent_child, old_node_size,
                 old_child_size, old_jump, changed_node, changed_child) = restore
                parent[changed_node] = old_parent_node
                parent[changed_child] = old_parent_child
                subtree[changed_node] = old_node_size
                subtree[changed_child] = old_child_size
                jump[0][changed_node] = old_jump
                rebuild(changed_node)
            continue
        neighbor = graph[node][index]
        frame[2] += 1
        if neighbor == father:
            continue
        answer += centroid_sum(neighbor)
        old_state = (parent[node], parent[neighbor], subtree[node],
                     subtree[neighbor], jump[0][node], node, neighbor)
        alternate = second if neighbor == first else first
        jump[0][node] = alternate
        rebuild(node)
        subtree[node] -= subtree[neighbor]
        subtree[neighbor] += subtree[node]
        parent[node] = neighbor
        parent[neighbor] = father
        answer += centroid_sum(node)
        child_first, child_second = largest_two(neighbor)
        stack.append([neighbor, node, 0, child_first, child_second, old_state])

    answers.append(str(answer))
print("\n".join(answers))

原有 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
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// main.cpp：用最大子树链倍增求每个连通块重心，换根枚举每条边两侧组件。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
const int LOGN = 20;

int n;
vector<int> g[MAXN];
int subtree_size[MAXN], parent_node[MAXN], heavy_son[MAXN];
int jump_heavy[MAXN][LOGN]; // 沿“最大子树儿子”链向下跳
long long answer;

void rebuild_jump(int u) {
    for (int i = 1; i < LOGN; i++) {
        jump_heavy[u][i] = jump_heavy[jump_heavy[u][i - 1]][i - 1];
    }
}

void add_centroid_sum(int root) {
    int u = root;

    // 沿最大子树方向向下跳，直到再往下会小于半棵树。
    for (int i = LOGN - 1; i >= 0; i--) {
        int v = jump_heavy[u][i];
        if (v != 0 && subtree_size[v] * 2 >= subtree_size[root]) {
            u = v;
        }
    }

    answer += u;
    if (subtree_size[u] * 2 == subtree_size[root]) {
        answer += parent_node[u];
    }
}

void dfs_prepare(int u, int fa) {
    parent_node[u] = fa;
    subtree_size[u] = 1;
    heavy_son[u] = 0;

    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) {
            continue;
        }
        dfs_prepare(v, u);
        subtree_size[u] += subtree_size[v];
        if (subtree_size[v] > subtree_size[heavy_son[u]]) {
            heavy_son[u] = v;
        }
    }

    jump_heavy[u][0] = heavy_son[u];
    rebuild_jump(u);
}

void dfs_reroot(int u, int fa) {
    int first = 0;
    int second = 0;

    // 找出当前 u 的最大、次大相邻组件。换根时要临时排除正在走向的儿子。
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (subtree_size[v] >= subtree_size[first]) {
            second = first;
            first = v;
        } else if (subtree_size[v] >= subtree_size[second]) {
            second = v;
        }
    }

    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) {
            continue;
        }

        // 删边 (u,v) 后，v 这一侧就是以 v 为根的连通块。
        add_centroid_sum(v);

        int old_size_u = subtree_size[u];
        int old_size_v = subtree_size[v];
        int old_parent_u = parent_node[u];
        int old_parent_v = parent_node[v];
        int old_jump_u = jump_heavy[u][0];

        // 临时把 u 这一侧看成一个以 u 为根的连通块。
        jump_heavy[u][0] = (v == first) ? second : first;
        rebuild_jump(u);
        subtree_size[u] -= subtree_size[v];
        subtree_size[v] += subtree_size[u];
        add_centroid_sum(u);

        // 换根进入 v 的方向。
        parent_node[u] = v;
        parent_node[v] = fa;
        dfs_reroot(v, u);

        // 恢复现场。
        parent_node[u] = old_parent_u;
        parent_node[v] = old_parent_v;
        subtree_size[u] = old_size_u;
        subtree_size[v] = old_size_v;
        jump_heavy[u][0] = old_jump_u;
        rebuild_jump(u);
    }
}

void solve_one() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        subtree_size[i] = 0;
        parent_node[i] = 0;
        heavy_son[i] = 0;
        for (int j = 0; j < LOGN; j++) {
            jump_heavy[i][j] = 0;
        }
    }

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

    answer = 0;
    dfs_prepare(1, 0);
    dfs_reroot(1, 0);
    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)。

总结

重心判定只看最大组件；把“沿最大组件走”做成倍增，换根就能在线完成。

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] 树的重心

目录

题意

思路

Python 知识

代码

复杂度

总结