[CSP-S 2019] 树的重心

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

枚举每条断边，两侧各求重心：沿“最大子树”方向下降的路线唯一，用重儿子链上的倍增跳表 O(log n) 定位；换根时只有当前端点需要重算重儿子与跳表。

OJ: luogu

题目 ID: P5666

难度:省选/NOI-

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

创建: 2026-07-16 23:59

更新: 2026-10-30 13:06

前置题目

luogu P1395会议树的重心定义与树形 DFS 基础 codeforces 685BKay and Snowflake子树重心的重链单调性定位与倍增/向上跳跃 luogu P3379【模板】最近公共祖先（LCA）树上倍增跳表的预处理与跳跃查询 luogu P3478[POI 2008] STA-Station树上换根 DP 基础与补树信息维护

形式化题目

给定一棵 $n$ 个点的无向树 $T=(V,E)$ ， $|V|=n$ ，每条边长度都是 $1$ 。

对树 $H$ ，若删去点 $c$ 后 $H$ 分裂出的每个连通块大小都不超过 $\lfloor |H|/2 \rfloor$ ，称 $c$ 是 $H$ 的重心。一个树的重心只有一个或两个。

对每条边 $e=(u,v)$ ，删去它后 $T$ 分裂为两个连通块 $T_u$ 、 $T_v$ 。要求

\sum_{e \in E}\ \Big(\sum_{c \in \mathrm{Cen}(T_u)} c \;+\; \sum_{c \in \mathrm{Cen}(T_v)} c\Big)

其中 $\mathrm{Cen}(H)$ 表示 $H$ 的重心集合。 $n \leqslant 3 \times 10^5$ ， $T \leqslant 5$ 组数据。

先看样例第一组： $n=5$ ，边为 $(1,2),(2,3),(2,4),(3,5)$ 。切掉边 $(1,2)$ 后，一侧只剩 $\{1\}$ ，另一侧是 $\{2,3,4,5\}$ 。小连通块的重心就是它自己；而 $4$ 个点那一侧有两个重心 $2$ 和 $3$ ，两个编号都要计入答案。

图上标了 $2 \times \mathrm{sz}(3) = 4 = m$ ，这正是出现两个重心的条件：某个方向的点数恰好是一半。后面所有推导都绕这一条判定条件展开。

暴力解法

思路

最直接的做法是枚举每条边，把两侧连通块各自求一遍重心。

求单个连通块的重心也不必逐点验证定义，可以沿「最大子树」方向走：把连通块内任一点当根，算出各子树的点数；只要存在一个子树点数超过 $\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/**
 * 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-10-01 21:04
 */
// brute.cpp：小数据暴力解。对每条边断开，两侧连通块分别以断边端点为根，
// 用“沿最大子树方向下降”在 O(size) 内找重心并累加编号和。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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 (auto v : g[u]) {
            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 (auto v : g[root]) {
        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 (auto v : g[cur]) {
            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);
        }

        ll 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;
}

复杂度

每条边断一次，两侧各做一次 $O(n)$ 的子树统计与下降，共 $n-1$ 条边，总 $O(n^2)$ 。 $n = 3 \times 10^5$ 时是 $10^{10}$ 量级，跑不完。

瓶颈

两个地方重复劳动：

统计重复。 每切一条边都要把两侧的子树大小从头算一遍，而这些信息在相邻两次切边之间几乎没变。
下降重复。 找重心要一步一步走，链状树上单次要潜到 $O(n)$ 深，所有边加起来就更慢。

正解：换根 + 重链倍增

先把上一节「沿最大子树方向下降」这条直觉钉死，再看它为什么能吃下倍增和换根两种加速。

观察一：下降方向唯一

以大小为 $m$ 的连通块内任一点 $u$ 为根。若某个子树 $A$ 满足 $\mathrm{sz}(A) > \lfloor m/2 \rfloor$ ，那么这样的子树至多一个。

反证：假设子树 $A$ 、 $B$ 都超过一半，则 $\mathrm{sz}(A) + \mathrm{sz}(B) > 2\lfloor m/2 \rfloor$ 。而 $A$ 、 $B$ 都在 $u$ 下方且互不相交，点数之和至多 $m-1$ 。两式矛盾。

于是「往最大的那个子树走」是唯一的方向，不会分支。从任意起点出发反复这样做，走的是一条确定的链。

观察二：沿链倍增，落点就是重心

沿这条链往下走，子树大小严格递减，所以「 $\mathrm{sz} \geqslant m/2$ 」这个条件沿链是单调的：前半段成立，后半段不成立。要的就是最后一个满足 $2\,\mathrm{sz}(x) \geqslant m$ 的点。

为什么停在那里就是重心？设落点为 $x$ ：

$x$ 的每个子树都不超过 $\lfloor m/2 \rfloor$ （否则还能继续往下走，与「最后一个」矛盾）；
$x$ 上方的部分是 $m - \mathrm{sz}(x) \leqslant \lfloor m/2 \rfloor$ （因为 $2\,\mathrm{sz}(x) \geqslant m$ ）。

两部分都不超过一半，所以 $x$ 是重心。

再看什么时候有两个重心。若 $2\,\mathrm{sz}(x) = m$ ，则 $x$ 上方的部分也恰好是 $m/2$ 。此时它的父节点 $p$ ：以 $p$ 为根时， $x$ 这一侧是 $m/2$ ，其余部分是 $m - m/2 = m/2$ ，同样都不超过一半，所以 $p$ 也是重心。两个重心必然相邻，且这条边两侧恰好各一半。

链上既然单调，就可以跳着走。预处理 $\mathrm{jump}[x][k]$ 表示从 $x$ 沿重儿子方向走 $2^k$ 步到达的点，查询时 $k$ 从 $19$ 递减到 $0$ ，能跳就跳：

图里 $m=4$ ：先试 $2^1$ 步落到 $5$ ， $2 \times 1 = 2 < 4$ 不够，不跳；再试 $2^0$ 步落到 $3$ ， $2 \times 2 = 4 \geqslant 4$ ，跳过去。停在 $3$ 后正好 $2\,\mathrm{sz}(3) = m$ ，于是父节点 $2$ 也是重心。整个过程 $O(\log n)$ 。

观察三：换根只需要补一个点

断边 $(u,v)$ 后把 $v$ 临时当根，树分成两半：

$v$ 这一侧就是原来以 $v$ 为根的子树，内部拓扑、 $\mathrm{sz}$ 、重儿子、跳表全都没变，直接按观察二查。
$u$ 这一侧是去掉那棵子树后的补树，大小为 $n - \mathrm{sz}(v)$ 。此时 $u$ 变成了 $v$ 的子节点，它的「子节点」集合从「原来的儿子」变成「除 $v$ 以外的所有邻居」。

关键在于改动的范围。 $\mathrm{jump}$ 是单向朝下跳的：任何点查重心时只会沿自己的重儿子往下走，永远走不回祖先。所以

$v$ 侧的点：子树没动，重儿子与跳表不用改；
$u$ 下方的点：它们的下行路径不经过 $u$ ，不用改；
$u$ 的祖先：它们的重儿子与 $\mathrm{sz}$ 都没变，不用改。

真正变的只有当前这个端点 $u$ 自己的重儿子，于是只重算 $\mathrm{jump}[u][\cdot]$ ， $O(\log n)$ 。

选「除 $v$ 以外最大的邻居」时不能临时扫邻接表：菊花图上 $u$ 的度数是 $O(n)$ ，扫一遍就退化。做法是预处理每个点的最大和次大邻居，断开的恰好是最大那个时就取次大，否则取最大， $O(1)$ 。

算法流程

第一遍 DFS 以 $1$ 为根，回溯时统计 $\mathrm{sz}$ 与重儿子，再按层建好跳表。第二遍用换根 DFS 枚举每条边：

为什么要「保存现场」和「回溯恢复」：第 ③ 步改的是全局数组，必须等两侧重心都查完才还原，否则下一条边会读到错的重儿子。换根 DFS 把这套「进入时改、退出时还原」的配对自然写在递归的进/出两个位置：进函数时把 fa、sz、jump[u][0] 存进局部变量，递归回来后再逐项写回。

有一处容易看错：代码在推进到 $v$ 时，为了能继续枚举 $v$ 的子边，真的把整棵树的定向根挪到了 $v$ （fa[u]=v、fa[v]=father、sz[v] += sz[u]），所以回溯时要恢复的是 $u$ 和 $v$ 两个点的 fa 与 sz，再加 jump[u][0] 与重建的 jump[u]。正文说「只改一个点」，指的是重儿子方向只有一个点要重选；根指针本身是另一回事。

代码

变量与正文的对应：sz[u] 是 $\mathrm{sz}(u)$ ，jump_table[u][k] 是 $\mathrm{jump}[u][k]$ ，son[u] 是重儿子，largest_two 求最大与次大邻居。

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/**
 * 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-10-30 14:12
 */
// main.cpp：对每条边断开，用“沿最大子树方向倍增”求两侧连通块的重心编号和。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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 son[MAXN];                // 初始定向下 i 的最大子节点（重儿子）
int jump_table[MAXN][LOGN];   // jump_table[i][k]：沿 heavy 链向下跳 2^k 步到达的点
ll 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 (auto v : g[u]) {
        if (sz[v] >= sz[first]) {
            second = first;
            first = v;
        } else if (sz[v] >= sz[second]) {
            second = v;
        }
    }
}

// 第一遍 DFS：以 1 为根填 fa，回溯时汇总 sz 并选出重儿子。
void dfs_init(int u, int p) {
    fa[u] = p;
    sz[u] = 1;
    son[u] = 0;
    for (auto v : g[u]) {
        if (v == p) {
            continue;
        }
        dfs_init(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) {
            son[u] = v;
        }
    }
}

// 第二遍：换根 DFS 枚举每条边，统计两侧重心。
//
// 进入 v 的子树前把 v 临时当根：u 的 heavy 方向换成“除 v 外最大的邻居”，
// sz[u]、sz[v]、fa 同步改；递归回来后再逆操作恢复。
// 因为切边只影响 u 一个点，其余节点零修改，所以每条边只需一次换根 + 一次恢复。
void dfs_reroot(int u, int p) {
    // 当前定向下 u 的最大、次大相邻组件，用于把某个儿子排除后重选 heavy 方向。
    int first, second;
    largest_two(u, first, second);

    for (auto v : g[u]) {
        if (v == p) {
            continue;
        }

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

        // 保存现场，准备把 v 临时变成定向根。
        int save_fa_u = fa[u], save_fa_v = fa[v];
        int save_sz_u = sz[u], save_sz_v = sz[v];
        int save_jump0_u = jump_table[u][0];

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

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

        // 更新父指针，进入 v 的子树继续枚举。
        fa[u] = v;
        fa[v] = p;
        dfs_reroot(v, u);

        // 恢复现场，回到“u 是当前定向根”的状态，继续处理 u 的下一个儿子。
        fa[u] = save_fa_u;
        fa[v] = save_fa_v;
        sz[u] = save_sz_u;
        sz[v] = save_sz_v;
        jump_table[u][0] = save_jump0_u;
        rebuild_jump(u);
    }
}

// 处理单组测试数据：读入、预处理、换根枚举每条边并累加重心编号和。
void solve_one() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        sz[i] = 1;
        fa[i] = 0;
        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 为根求 fa、sz、son。
    dfs_init(1, 0);

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

三个值得对照代码看的细节：

add_centroid_sum 里 sz[v] * 2 >= total 就是观察二的判定，最后一行 sz[u] * 2 == total 则补上双重心时的父节点。
rebuild_jump 只重算 $k \geqslant 1$ 的层，第 $0$ 层由调用方直接赋值。
largest_two 在进入 $u$ 时算一次并存进局部变量 first/second，之后 $u$ 的每个儿子都 $O(1)$ 取用。

复杂度

时间：预处理 $\mathrm{sz}$ 与跳表 $O(n\log n)$ ；枚举 $n-1$ 条边，每边两次查询、一次单点重建、一次回溯恢复，各 $O(\log n)$ 。总 $O(n \log n)$ 。
空间：跳表 $O(n \log n)$ ，邻接表 $O(n)$ 。取 $\log n = 20$ 时约 40 MB。

总结

这题把「求重心」拆成了两件可以独立加速的事：

c \text{ 是重心} \iff \text{每个方向的点数} \leqslant \lfloor m/2 \rfloor

一条判定条件，配上「超过一半的方向至多一个」，就把逐点验证变成了沿唯一链下降；链上 $\mathrm{sz}$ 单调，于是下降能吃倍增；而断边只让一个端点的重儿子失效，于是换根能吃 $O(\log n)$ 的局部修补。

两个容易踩的地方：

别在断边时扫邻接表找次大邻居。 菊花图上单次就退化到 $O(n)$ ，必须预处理最大与次大。
跳表只朝下，所以改一个点不会波及祖先。 这条是换根能成立的全部理由；如果哪天把跳表改成朝上或双向，这个结论立刻失效。

参考与致谢

来源	借鉴的思路	本文自行补充
xht（uid 100544）	对比「按点统计贡献」与「按边求两侧重心」两类路线	采用换根 + 重链倍增路线；补写唯一方向、双重心论证
rainygame（uid 804607）	以最大子树方向唯一为依据，把找重心转为沿重儿子链下降	补充倍增判定与边界说明，对齐本地实现
TEoS（uid 91534）	以重心为根、重链与次重儿子切换的线性路线	作为复杂度与实现取舍的比较材料
1gnat2（uid 2508）	沿子树重心祖先路径推进、批量处理补树重心	作为渐进更优的比较路线，未采纳为主解

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$ 。保证给出的图是一个树。