树的重心

一句话算法

删掉一个点，看剩下的最大连通块有多大；让这个最大块尽量小的点，就是树的重心。一次 DFS 统计子树大小，就能在线性时间内找出全部重心。

阅读前建议先掌握 [ Rbook: 树的入门] 和 [ Rbook: DFS序] 中的子树大小。本文先从删点后的连通块出发，推导判定式，再说明重心的性质，给出可复用模板与完整程序。模板的预处理与 [ Rbook: 树链剖分（HLD）] 同形：如果你已经为别的操作做过树链剖分，重心几乎可以白拿。最后给出倍增跳表下降版本，把“沿重链下走”从 $O(\text{链长})$ 压成 $O(\log n)$ ，可在同一棵树上反复查询任意连通块的重心。

1 问题模型

给定一棵有 $n$ 个节点的无权树，节点编号为 1..n。删除节点 $u$ 以及与它相连的边后，树会分成若干个连通块。

记这些连通块的最大点数为 $B(u)$ 。使 $B(u)$ 最小的点称为树的重心，答案可能不止一个。单点树删除唯一的节点后没有剩余连通块，约定此时 $B(u)=0$ 。

重心还有一个等价判定：

u\text{ 是重心}\quad\Longleftrightarrow\quad B(u)\leqslant\left\lfloor\frac n2\right\rfloor.

这里比较的是原树节点数的一半，即 n / 2，不是剩余节点数的一半。本文先按“最大块最小”求解，再证明两个定义为什么等价。

2 核心直觉

想象删除一个路口后，树被切成几片。重心要控制的是最大那一片的点数，而不是路口的度数、到叶子的距离或画面上的位置。

如果从某个点看出去，有一个方向包含超过一半的节点，那么树向这个方向偏重。沿该方向移动一步，原来的大块会缩小，而身后那一块不足一半，最大块就会变小。

树有 9 个点，删除 u 后两侧分别有 2 个点和 6 个点；向较大的连通块移动

图中 $n=9$ ，删除 u 后的最大块有 6 个点。向相邻点 v 移动后，u 方向只有 3 个点，其余块都来自原来的 6 个点，并且不再包含 v，因此 $B(v)<6$ 。

这个观察解释了“为什么向大块走”。实际求全部重心时，无需逐点尝试删树：只要知道每个方向有多少点，就能直接计算 $B(u)$ 。

3 从子树大小得到判定式

任选一个点作为 DFS 的根，例如 1。设 sz[u] 是 u 的子树大小，包含 u 自己。

删除 u 后，各方向的连通块只有两类：

方向	连通块大小	原因
每个儿子 `v` 的方向	`sz[v]`	`v` 的整棵子树仍连通
父亲方向	`n - sz[u]`	`u` 的子树以外，所有节点仍连通

因此：

B(u)=\max\left(\{n-sz[u]\}\cup\{sz[v]\mid v\text{ 是 }u\text{ 的儿子}\}\right).

根没有父亲，n - sz[root] = 0，公式仍然成立。叶子没有儿子，最大块就是父亲方向的 n-1 个点；单点树则得到 0。

注意

只检查儿子会漏掉父亲方向。sz[u] 必须先累加完整，再计算 n - sz[u]；否则算到的并不是删除 u 后的连通块大小。

3.1 用一棵树算一遍

以下面这棵树为例，以 1 为 DFS 根。图中双圈表示重心，节点内部仅显示原编号。

八个节点的树，重心为相邻的节点 1 和 3

节点 `u`	`sz[u]`	儿子方向的块大小	父亲方向 `n - sz[u]`	`B(u)`	是否为重心
1	8	3、4	0	4	是
2	3	1、1	5	5	否
3	4	3	4	4	是
4	1	无	7	7	否
5	1	无	7	7	否
6	3	1、1	5	5	否
7	1	无	7	7	否
8	1	无	7	7	否

最小的平衡值是 4，在节点 1、3 取得。删除 1 后，两块大小为 3、4；删除 3 后，两块大小为 4、3，都不超过 $n/2=4$ 。

节点 2 的两个儿子都只有 1 个点，但它不是重心，因为父亲方向还有 5 个点。换一个 DFS 根会改变 sz 和父子关系，却不会改变删点后的真实连通块，所以 B(u) 和重心集合与 DFS 根无关。

4 关键数组与算法步骤

名称	含义
`g[u]`	节点 `u` 的邻接表
`fa[u]`	DFS 中 `u` 的父亲，根的父亲为 `0`
`sz[u]`	以当前 DFS 根为准的子树大小
`son[u]`	`u` 的重儿子，即子树最大的儿子，叶子为 `0`；与树链剖分里的同名数组一致
`balance[u]`	删除 `u` 后的最大连通块大小，即 $B(u)$
`best`	所有 `balance[u]` 的最小值
`ans`	全部重心，按编号升序排列

按照递归 DFS 的思路，处理一个节点只需要下面几步：

dfs1(u, father):
    fa[u] = father
    sz[u] = 1
    son[u] = 0
    对每个儿子 v:
        dfs1(v, u)
        sz[u] += sz[v]
        若 sz[v] > sz[son[u]]，则 son[u] = v
    balance[u] = max(sz[son[u]], n - sz[u])

这里多维护了一个 son[u]。因为它是“子树最大的儿子”，儿子方向的最大块恰好就是 sz[son[u]]，所以 balance[u] 在回溯时一次就能算完，不需要再存一份访问顺序逆着扫第二遍。处理完所有节点后，先找最小的 balance[u]，再按编号扫描，收集所有取到最小值的节点。

4.1 递归 dfs1：和树链剖分同一套预处理

C++ 模板直接沿用 [ Rbook: 树链剖分（HLD）] 的写法：const int maxn 加全局数组、递归 dfs1，一遍 DFS 同时得到 fa、sz、son、balance。这样写的实际好处是重心可以寄生在 HLD 的预处理上：如果题目已经为了路径操作做过剖分，sz 和 son 早就在手，求重心只多一行赋值和一次扫描。

代价是递归深度：链形树的 dfs1 会递归 $n$ 层，栈限额要留够。

4.2 沿重链走：不扫全树也能找到重心

有了 son，还可以换一种收集方式。从 build 的根出发，只要重儿子的子树还超过一半就继续往下走：

u = root
while son[u] != 0 且 2 * sz[son[u]] > n:
    u = son[u]
此时 u 是重心；若 2 * sz[son[u]] == n，son[u] 也是重心

这既是 HLD 味道最重的写法，也解释了“重心为什么总在重链上”。复杂度是 $O(\text{重链长度})$ ，最好情况下远小于扫全树；但它依赖 sz 和 son 已经按同一个根算好，所以放在 build 之后用。

4.3 倍增跳表下降：把重链下走压成 $O(\log n)$

上面的 while 一次只走一步，链形树上重链长度是 $O(n)$ ，单次查询就退化到 $O(n)$ 。但这条链有一个很好的单调性：沿重链往下走，sz 严格递减。于是“2 * sz[x] >= m 是否成立”在重链上是一个从真到假的前缀，可以倍增跳跃：

up[u][0] = son[u]
up[u][k] = up[ up[u][k-1] ][k-1]

u = 待查连通块的根，m = sz[u]
for k = LOGN-1 downto 0:
    v = up[u][k]
    若 v != 0 且 2 * sz[v] >= m，则 u = v      // 能跳就跳
最终 u 是重心；若 2 * sz[u] == m，fa[u] 也是重心

这就是倍增跳跃的通用套路：大步到小步试探、能跳就跳，把一次“走到底”换成 $O(\log n)$ 次判断。原理可参考 [ Rbook: binary jump]，写法和倍增 LCA 的跳表完全同形，只是方向相反——LCA 沿父亲往上跳，这里沿重儿子往下跳。

以一个 $7$ 个点的链 1-2-3-4-5-6-7 为例，以 1 为根，重链就是整条链，sz = 7,6,5,4,3,2,1：

m = 7
k=2: up[1][2] = 5，sz[5]*2 = 6 < 7   -> 不跳
k=1: up[1][1] = 3，sz[3]*2 = 10 >= 7  -> 跳到 3
k=0: up[3][0] = 4，sz[4]*2 = 8 >= 7   -> 跳到 4
停下：u = 4，sz[4]*2 = 8 != 7，唯一重心 4

两次跳跃就从链头落到了中点，而朴素 while 要走 $3$ 步。链越长，差距越大：重链长度 $L$ 的朴素写法要 $L$ 步，倍增只要 $\lceil\log_2 L\rceil$ 次判断。

说明

用 >= 而不是 >。 写成 2 * sz[v] >= m 时，跳表会一路跳到“恰好一半”的那个点，此时 fa[u] 也是重心，补一句判断就能同时拿到两个重心。若写成 >，跳表会停在双重心里靠上的那个，也能靠 son 补出另一个，但两种情况要分开写，不如统一用 >= 干净。

4.4 为什么这个接口能查“任意连通块”

centroid_of_subtree(u) 查的是以 u 为根、大小为 sz[u] 的那个连通块，而不是整棵树。这一点是删边类题目的关键：切掉一条边 (p, u)（p 是 u 的父亲）后，u 一侧恰好就是子树 u，内部结构完全没变，所以 sz、son、up 全部可以照用，一次 O(log n) 查询就得到这侧的重心。

另一侧（p 一侧）是“补树”，p 的儿子集合少了 u，必须改信息才能查：把 p 的重儿子换成“除 u 外最大的邻居”，同步改 sz[p] 和 fa，再重建 p 这一层的跳表。因为切边只影响 p 一个点，其余节点零修改，所以整趟枚举每条边仍是 $O(n \log n)$ 。

这就是 [ Rbook: binary jump] 里“跳表可复用”的直接收益：预处理一次，之后每个连通块单独 $O(\log n)$ 。

说明

Python 版用 array('i') 存跳表。 把 up 写成 [[0]*(n+1) for _ in range(LOGN)] 看起来自然，但每个格子是一个独立的 Python int 对象， $n=3\times10^5$ 时要 150MB 以上；换成 array('i') 后每格 4 字节，整张表约 23MB，实测峰值从 160MB 降到 140MB（剩下的主要是邻接表的 list 开销）。

5 算法证明

5.1 子树大小与最大块都计算正确

叶子的子树只有自己，sz[u]=1。对于非叶子，回溯时每个儿子的子树大小都已正确算出。u 的子树恰好由自己与所有儿子的子树组成，因此：

sz[u]=1+\sum_{v\text{ 是 }u\text{ 的儿子}}sz[v].

树上两点之间只有一条简单路径。删除 u 后，不同儿子方向无法再相互连通，父亲方向也无法绕到某个儿子方向。因此上面的各块恰好覆盖全部剩余节点，既不遗漏也不重叠，balance[u] 就是 $B(u)$ 。

扫描所有节点并取 $B(u)$ 的最小值，得到的就是定义要求的全部重心。

5.2 为什么重心的最大块不超过一半

设 u 已经使 $B(u)$ 最小，却有一个连通块 $C$ 的大小 $m>n/2$ 。取 $C$ 中与 u 相邻的节点 v。

删除 v 后，朝 u 方向的块有 $n-m<m$ 个点；其他块都包含在 $C\setminus\{v\}$ 中，每块至多 $m-1$ 个点。因此 $B(v)<m=B(u)$ ，与 u 的最小性矛盾。

所以任何重心都满足 $B(u)\leqslant n/2$ 。有限个节点中必然存在最小值，这也说明每棵非空树都存在重心。

5.3 为什么不超过一半就已经最优

设 $B(u)\leqslant n/2$ ，任取另一个点 v。删除 u 后，包含 v 的块记为 $C$ ，大小为 $s$ ，则 $s\leqslant B(u)$ 。

删除 v 时， $C$ 以外的所有节点仍通过 u 连成一块，至少有 $n-s$ 个点。因此：

B(v)\geqslant n-s\geqslant n-B(u)\geqslant B(u).

所以任何其他点都不能比 u 更好，u 就是重心。结合前一节，两个定义等价。

5.4 为什么重心在根出发的重链上

设当前点 u 的重儿子 v 满足 $2\,sz[v]>n$ 。

先看 u： $B(u)\geqslant sz[v]>n/2$ ，所以 u 不是重心。

再看 v 子树以外的任意点 x：删除 x 后，v 的整棵子树仍然连通（x 不在其中），所以包含它的块至少有 $sz[v]>n/2$ 个点，x 也不是重心。

于是重心只能藏在 v 的子树里，而 v 就是重儿子。不断重复这个判断，重心只能沿着“根 → 重儿子 → 重儿子 → …”这条重链往下走，不会拐进任何轻儿子。

停在第一个满足 $2\,sz[son[u]]\leqslant n$ 的点 u 上时，它一定满足平衡条件：可以从重链上走下来，说明来自父亲方向的那块超过一半，因此 $n-sz[u]<n/2$ （u 就是根时没有父亲方向， $n-sz[u]=0$ 同样成立）；而儿子方向最大块就是 $sz[son[u]]\leqslant n/2$ 。两个方向都不超过一半，u 就是重心。

5.5 为什么跳表不会跳过头

倍增下降的每一跳都要求 $2\,sz[v]\geqslant m$ ，也就是“跳过去之后，v 的子节点方向仍可能占一半以上”。这保证了两个不变量：

不会跳错方向。 若 $2\,sz[v]\geqslant m$ ，v 的子树占了连通块一半以上，删除 v 子树以外的任何点，这块仍然完整连通且不少于一半，所以重心只可能在 v 的子树里。跳进 v 不会丢失答案。
不会跳过目标。 目标是“最后一个满足 $2\,sz[x]\geqslant m$ 的重链点”。sz 沿重链严格递减，满足条件的点构成链上的一个前缀，所以这个目标唯一存在，贪心跳到不能再跳就正好停在它上面。

停下时，重链上再往下一步就有 $2\,sz[son[u]]<m$ ，即儿子方向最大块不足一半；而 u 是从上一步跳下来的，说明父亲方向那块 $m-sz[u]$ 也不超过一半（u 是起点时该项为 $0$ ）。因此 $B(u)\leqslant\lfloor m/2\rfloor$ ，u 是重心。

6 复杂度分析

时间复杂度： $O(n)$ 。一次 dfs1 汇总 sz、son、balance，再线性扫一遍收集答案，都只处理线性数量的节点或边。沿重链走的写法额外花 $O(\text{重链长度})\leqslant O(n)$ ，且不必扫全树。
空间复杂度： $O(n)$ 。邻接表与 fa、sz、son、balance 均占线性空间。
递归深度：链形树上 dfs1 递归 $n$ 层，最坏占 $O(n)$ 栈空间。

倍增跳表版（tree_centroid_jump.cpp）的账要分开算：

预处理： $O(n\log n)$ 。up 有 $n \times \log n$ 个格子，按层填一遍。
单次查询： $O(\log n)$ 。跳表从高位到低位扫一遍，LOGN 次判断。
空间： $O(n\log n)$ ，up 是唯一的额外开销；fa、sz、son 仍是 $O(n)$ 。
整棵树求一次重心： $O(n\log n)$ ，比扫全树的 $O(n)$ 慢；它的价值在于同一棵树上要反复查很多连通块时，把每次的 $O(n)$ 换成 $O(\log n)$ 。删边枚举每条边共 $2(n-1)$ 次查询，总 $O(n\log n)$ ，这时才划算。

答案由按编号扫描得到，因此无需额外排序。

7 代码模板

两份模板的预处理思路相同（一遍 dfs1 求出 sz，用重儿子表示儿子方向的最大块），C++ 沿用 HLD 的全局数组加 dfs1/build，Python 用动态列表加同名 dfs1/build。都不使用 struct / class。

另外两份是倍增跳表下降版（tree_centroid_jump.cpp / .py），接口多出一个“查任意连通块”的入口：

能力	扫全树版	倍增跳表版
预处理	`build(root=1)`	`build(root=1)`
整棵树的重心	`ans`（`build` 后已填好）	`centroid_all()`
任意连通块的重心	无	`centroid_of_subtree(u)`
重链下走	`centroid_on_heavy_path()`， $O(\text{链长})$	`centroid_of_subtree(u)`， $O(\log n)$
额外空间	$O(n)$	$O(n\log n)$

什么时候用哪一份：只需要一次重心、且不要求快速反复查询时，用扫全树版，代码短、常数小、内存省；需要在同一棵树上反复查大量连通块（删边、换根、重心分治的候选评估）时，用倍增跳表版，把每次 $O(n)$ 换成 $O(\log n)$ 。

C++ 接口	Python 接口	用途
`init(n)`	`init(n)`	清空旧图，每组新数据调用一次；C++ 只清 `g`，其余数组由 `dfs1` 逐点覆写
`add_edge(u, v)`	`add_edge(u, v)`	添加无向边，两端都会写入邻接表
`build(root=1)`	`find_centroids(root=1)`	求全部重心，填充 `balance`、`best`、`ans`；Python 版返回升序列表
`centroid_on_heavy_path()`	`centroid_on_heavy_path()`	沿重链求重心（至多两个，升序），需在同一次 `build` / `find_centroids` 之后调用
`balance[u]`、`best`	同名	查询删除某点后的最大连通块大小、以及重心的平衡值

扫全树版的接口表如上；倍增跳表版另有 centroid_of_subtree(u) 与 centroid_all()，见下一节。

C++ 调用顺序是 init(n) → 添加 n-1 条边 → build()，答案在 ans 里；Python 是 init(n) → 添加 n-1 条边 → find_centroids() 取返回值。要求 $n\geqslant1$ ，编号和根均在 1..n 内，输入是连通无环的树。可以在同一棵树上更换根重复 build，重心集合不会改变；但 centroid_on_heavy_path() 依赖最近一次 build 的父子关系，要和它配对使用。

C++
Python

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

// 树的重心，HLD 风格：1 下标、全局数组，预处理与树链剖分的 dfs1 完全同形。
// 约定：输入是连通无环的树，n >= 1，节点编号为 1..n。
const int maxn = 300000 + 5;

int n;
vector<int> g[maxn];

/*------------------------ 树的重心 代码 开始 ------------------------*/
int fa[maxn];      // fa[u]：父亲，根的 fa 为 0
int sz[maxn];      // sz[u]：子树大小（含自己）
int son[maxn];     // son[u]：重儿子，叶子为 0
int balance[maxn]; // balance[u]：删除 u 后的最大连通块大小 B(u)
int best;          // 所有 B(u) 的最小值
int root;          // 当前 DFS 根，重链走法要从它出发
vector<int> ans;   // 全部重心，编号升序

void init(int node_count) {
    n = node_count;
    // fa / sz / son / balance 会被 dfs1 逐点覆写，只需清空旧图。
    for (int u = 1; u <= n; ++u) g[u].clear();
}

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 第一遍 DFS（与 hld 的 dfs1 同形）：往下填 fa，回溯时汇总 sz 并选出重儿子。
// 回到 u 时 sz[u]、son[u] 都已确定，而 n 一开始就知道，所以
// B(u) = max(儿子方向最大块, 父亲方向 n - sz[u]) 可以就地算完。
void dfs1(int u, int father) {
    fa[u] = father;
    sz[u] = 1;
    son[u] = 0;
    for (int v : g[u]) {
        if (v == father) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v; // sz[0] 恒为 0，叶子自然没有重儿子
    }
    balance[u] = max(sz[son[u]], n - sz[u]); // 重儿子就是最大的那个儿子
    best = min(best, balance[u]);
}

// 预处理入口：加完边之后调用一次，同时得到 balance[1..n]、best 和全部重心 ans。
// root 只影响父子关系，不影响答案。
void build(int start = 1) {
    root = start;
    best = n;
    dfs1(root, 0);
    ans.clear();
    for (int u = 1; u <= n; ++u) {
        if (balance[u] == best) ans.push_back(u);
    }
}

// 只求重心、不扫全树：重心一定落在 build 那个 root 出发的重链上。
// 重儿子子树 > n/2 时父亲方向 < n/2，重心只能更深；停下即为重心。
// 若重儿子子树恰为 n/2，它也是重心（第二个重心只能是它）。
// 依赖 build() 填好的 sz / son，也可以直接复用已有 HLD 的这两个数组。
vector<int> centroid_on_heavy_path() {
    int u = root;
    while (son[u] && sz[son[u]] * 2 > n) u = son[u];
    vector<int> res;
    res.push_back(u);
    if (son[u] && sz[son[u]] * 2 == n) res.push_back(son[u]);
    sort(res.begin(), res.end()); // 至多两个，保证编号升序
    return res;
}
/*------------------------ 树的重心 代码 结束 ------------------------*/

# 树的重心：节点编号为 1..n，输入必须是连通无环的树，n >= 1。
# 预处理与 C++ 版同形：递归 dfs1 一次求出 sz、son、balance。
# 链形树会递归 n 层，Python 3.12+ 的递归帧在堆上，放宽上限即可。
import sys

n = 0
best = 0
g = []
fa = []
sz = []
son = []
balance = []
ans = []


def init(node_count):
    global n, best, g, fa, sz, son, balance, ans
    n = node_count
    # 链形树上 dfs1 会递归 n 层，先把递归上限放开。
    sys.setrecursionlimit(max(3_000_000, node_count * 4))
    best = n
    g = [[] for _ in range(n + 1)]
    fa = [0] * (n + 1)
    sz = [0] * (n + 1)
    son = [0] * (n + 1)
    balance = [0] * (n + 1)
    ans = []


def add_edge(u, v):
    g[u].append(v)
    g[v].append(u)


def dfs1(u, father):
    """往下填 fa，回溯时汇总 sz、选出重儿子，并就地算出 B(u)。"""
    global best
    fa[u] = father
    sz[u] = 1
    son[u] = 0
    for v in g[u]:
        if v == father:
            continue
        dfs1(v, u)
        sz[u] += sz[v]
        if sz[v] > sz[son[u]]:   # sz[0] 恒为 0，叶子自然没有重儿子
            son[u] = v
    # 重儿子就是最大的那个儿子，父亲方向必须等 sz[u] 完整后再算。
    balance[u] = max(sz[son[u]], n - sz[u])
    best = min(best, balance[u])


def find_centroids(root=1):
    """返回全部重心（编号升序），更新 fa、sz、son、balance、best。"""
    global best, ans
    best = n
    dfs1(root, 0)
    ans = [u for u in range(1, n + 1) if balance[u] == best]
    return ans


def centroid_on_heavy_path():
    """沿重链求重心（至多两个，编号升序），需在同一次 find_centroids 之后调用。"""
    u = 1
    while son[u] and sz[son[u]] * 2 > n:
        u = son[u]
    res = [u]
    if son[u] and sz[son[u]] * 2 == n:
        res.append(son[u])
    res.sort()
    return res

倍增跳表下降版：

C++
Python

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

// 树的重心（倍增跳表下降版）：把“沿重链一步步下走”压成 O(log n)。
// 约定：输入是连通无环的树，n >= 1，节点编号为 1..n。
// maxn / LOGN 按 n 的上限调整：必须保证 2^LOGN > n。
const int maxn = 300000 + 5;
const int LOGN = 20; // 2^19 = 524288 > 3e5

int n;
vector<int> g[maxn];

/*------------------------ 倍增跳表下降求重心 代码 开始 ------------------------*/
int fa[maxn];       // fa[u]：父亲，根的 fa 为 0
int sz[maxn];       // sz[u]：子树大小（含自己）
int son[maxn];      // son[u]：重儿子，叶子为 0
int up[maxn][LOGN]; // up[u][k]：沿重链从 u 向下跳 2^k 步到达的点，跳出叶子为 0
int root_node;      // build 的根，重链从这里出发
vector<int> ans;    // 重心结果，编号升序

void init(int node_count) {
    n = node_count;
    // fa / sz / son / up 会被 dfs1 与 build_jump 逐点覆写，只需清空旧图。
    for (int u = 1; u <= n; ++u) g[u].clear();
}

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 第一遍 DFS：与 hld 的 dfs1 同形，往下填 fa，回溯时汇总 sz 并选出重儿子。
// 回到 u 时 sz[u]、son[u] 都已确定，重链的第 0 层 up[u][0] 也就定了。
void dfs1(int u, int father) {
    fa[u] = father;
    sz[u] = 1;
    son[u] = 0;
    for (int v : g[u]) {
        if (v == father) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v; // sz[0] 恒为 0，叶子自然没有重儿子
    }
    up[u][0] = son[u];
}

// 第二遍：按层搭跳表。up[u][k] = up[ up[u][k-1] ][k-1]。
// 必须外层枚举 k：第 k 层只依赖第 k-1 层，这样才能保证被跳到的点已经算好。
void build_jump() {
    for (int k = 1; k < LOGN; ++k)
        for (int u = 1; u <= n; ++u)
            up[u][k] = up[up[u][k - 1]][k - 1];
}

// 预处理入口：加完边之后调用一次。root 只决定父子关系，不影响重心集合。
void build(int start = 1) {
    root_node = start;
    dfs1(root_node, 0);
    build_jump();
}

// 求“以 u 为根、大小为 sz[u] 的连通块”的全部重心（编号升序，至多两个）。
// 沿重链向下走：只要某个方向的点还不少于连通块的一半，重心必在那一侧。
// 重链上 sz 严格递减，所以“2*sz[x] >= m”沿链单调，可用跳表大步到小步贪心下降。
vector<int> centroid_of_subtree(int u) {
    int m = sz[u]; // 当前连通块的总点数
    for (int k = LOGN - 1; k >= 0; --k) {
        int v = up[u][k];
        if (v != 0 && sz[v] * 2 >= m) u = v; // 能跳就跳
    }
    ans.clear();
    ans.push_back(u); // u 的子节点方向都不足一半，它一定是重心
    if (sz[u] * 2 == m) ans.push_back(fa[u]); // 恰好一半：父节点也是重心
    sort(ans.begin(), ans.end()); // 至多两个，保证编号升序
    return ans;
}

// 整棵树的重心，就是根这一侧连通块的答案。
vector<int> centroid_all() {
    return centroid_of_subtree(root_node);
}
/*------------------------ 倍增跳表下降求重心 代码 结束 ------------------------*/

# 树的重心（倍增跳表下降版）：把“沿重链一步步下走”压成 O(log n)。
# 节点编号 1..n，输入必须是连通无环的树，n >= 1。
# dfs1 是递归写法，与 C++ 版同形；Python 的递归帧在堆上，
# 用 sys.setrecursionlimit() 放宽上限即可跑链形树。
import sys
from array import array

n = 0
g = []
fa = []
sz = []
son = []
up = []      # up[k][u]：沿重链从 u 向下跳 2^k 步到达的点，跳出叶子为 0
root_node = 0
ans = []


def init(node_count):
    global n, g, fa, sz, son, up, ans
    n = node_count
    # 链形树上 dfs1 会递归 n 层，先把递归上限放开。
    sys.setrecursionlimit(max(3_000_000, node_count * 4))
    g = [[] for _ in range(n + 1)]
    fa = [0] * (n + 1)
    sz = [0] * (n + 1)
    son = [0] * (n + 1)
    up = []
    ans = []


def add_edge(u, v):
    g[u].append(v)
    g[v].append(u)


def dfs1(u, father):
    """往下填 fa，回溯时汇总 sz、选出重儿子，并顺手定下跳表第 0 层。"""
    fa[u] = father
    sz[u] = 1
    son[u] = 0
    for v in g[u]:
        if v == father:
            continue
        dfs1(v, u)
        sz[u] += sz[v]
        if sz[v] > sz[son[u]]:   # sz[0] 恒为 0，叶子自然没有重儿子
            son[u] = v
    up[0][u] = son[u]


def build(start=1):
    """dfs1 求 fa / sz / son / up[0]，再按层搭跳表。root 不影响重心集合。"""
    global root_node, up
    root_node = start
    LOGN = max(1, n.bit_length())      # 2^LOGN > n
    # 用 array('i') 存跳表：每个格子 4 字节，n=3e5 时全表约 23MB，
    # 换成 list 会因为每个 int 是独立对象而涨到 150MB 以上。
    up = [array('i', bytes(4 * (n + 1))) for _ in range(LOGN)]
    dfs1(start, 0)

    # 按层搭跳表：up[k][u] = up[k-1][ up[k-1][u] ]。
    # 外层枚举 k，保证第 k 层用到第 k-1 层时已经算好。
    for k in range(1, LOGN):
        prev, cur = up[k - 1], up[k]
        for u in range(1, n + 1):
            cur[u] = prev[prev[u]]


def centroid_of_subtree(u):
    """以 u 为根、大小为 sz[u] 的连通块的全部重心（编号升序，至多两个）。"""
    global ans
    m = sz[u]                      # 当前连通块的总点数
    for k in range(len(up) - 1, -1, -1):
        v = up[k][u]
        if v and sz[v] * 2 >= m:   # 能跳就跳
            u = v
    ans = [u]                      # 子节点方向都不足一半，u 一定是重心
    if sz[u] * 2 == m:             # 恰好一半：父节点也是重心
        ans.append(fa[u])
    ans.sort()
    return ans


def centroid_all():
    """整棵树的重心，就是根这一侧连通块的答案。"""
    return centroid_of_subtree(root_node)

另一种收集答案的方法是直接检查 balance[u] <= n / 2，Python 写成 balance[u] <= n // 2。两者与取最小值完全等价；本文保留 best，方便需要输出最优平衡值的题目复用。

8 完整代码

输入格式：第一行是节点数 n，接下来 n-1 行，每行两个整数 u v，表示一条无向边。

输出格式：第一行输出重心个数；第二行按编号升序输出全部重心，编号之间用空格分隔。下面四份程序都包含模板和读入输出，可以独立运行，输出格式一致。

C++
Python

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

// 树的重心，HLD 风格：1 下标、全局数组，预处理与树链剖分的 dfs1 完全同形。
// 约定：输入是连通无环的树，n >= 1，节点编号为 1..n。
const int maxn = 300000 + 5;

int n;
vector<int> g[maxn];

/*------------------------ 树的重心 代码 开始 ------------------------*/
int fa[maxn];      // fa[u]：父亲，根的 fa 为 0
int sz[maxn];      // sz[u]：子树大小（含自己）
int son[maxn];     // son[u]：重儿子，叶子为 0
int balance[maxn]; // balance[u]：删除 u 后的最大连通块大小 B(u)
int best;          // 所有 B(u) 的最小值
int root;          // 当前 DFS 根，重链走法要从它出发
vector<int> ans;   // 全部重心，编号升序

void init(int node_count) {
    n = node_count;
    // fa / sz / son / balance 会被 dfs1 逐点覆写，只需清空旧图。
    for (int u = 1; u <= n; ++u) g[u].clear();
}

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 第一遍 DFS（与 hld 的 dfs1 同形）：往下填 fa，回溯时汇总 sz 并选出重儿子。
// 回到 u 时 sz[u]、son[u] 都已确定，而 n 一开始就知道，所以
// B(u) = max(儿子方向最大块, 父亲方向 n - sz[u]) 可以就地算完。
void dfs1(int u, int father) {
    fa[u] = father;
    sz[u] = 1;
    son[u] = 0;
    for (int v : g[u]) {
        if (v == father) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v; // sz[0] 恒为 0，叶子自然没有重儿子
    }
    balance[u] = max(sz[son[u]], n - sz[u]); // 重儿子就是最大的那个儿子
    best = min(best, balance[u]);
}

// 预处理入口：加完边之后调用一次，同时得到 balance[1..n]、best 和全部重心 ans。
// root 只影响父子关系，不影响答案。
void build(int start = 1) {
    root = start;
    best = n;
    dfs1(root, 0);
    ans.clear();
    for (int u = 1; u <= n; ++u) {
        if (balance[u] == best) ans.push_back(u);
    }
}

// 只求重心、不扫全树：重心一定落在 build 那个 root 出发的重链上。
// 重儿子子树 > n/2 时父亲方向 < n/2，重心只能更深；停下即为重心。
// 若重儿子子树恰为 n/2，它也是重心（第二个重心只能是它）。
// 依赖 build() 填好的 sz / son，也可以直接复用已有 HLD 的这两个数组。
vector<int> centroid_on_heavy_path() {
    int u = root;
    while (son[u] && sz[son[u]] * 2 > n) u = son[u];
    vector<int> res;
    res.push_back(u);
    if (son[u] && sz[son[u]] * 2 == n) res.push_back(son[u]);
    sort(res.begin(), res.end()); // 至多两个，保证编号升序
    return res;
}
/*------------------------ 树的重心 代码 结束 ------------------------*/

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

    int node_count;
    if (!(cin >> node_count)) return 0;
    init(node_count);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }
    build();
    cout << ans.size() << '\n';
    for (int i = 0; i < (int)ans.size(); ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

# 树的重心：节点编号为 1..n，输入必须是连通无环的树，n >= 1。
# 预处理与 C++ 版同形：递归 dfs1 一次求出 sz、son、balance。
# 链形树会递归 n 层，Python 3.12+ 的递归帧在堆上，放宽上限即可。
import sys

n = 0
best = 0
g = []
fa = []
sz = []
son = []
balance = []
ans = []


def init(node_count):
    global n, best, g, fa, sz, son, balance, ans
    n = node_count
    # 链形树上 dfs1 会递归 n 层，先把递归上限放开。
    sys.setrecursionlimit(max(3_000_000, node_count * 4))
    best = n
    g = [[] for _ in range(n + 1)]
    fa = [0] * (n + 1)
    sz = [0] * (n + 1)
    son = [0] * (n + 1)
    balance = [0] * (n + 1)
    ans = []


def add_edge(u, v):
    g[u].append(v)
    g[v].append(u)


def dfs1(u, father):
    """往下填 fa，回溯时汇总 sz、选出重儿子，并就地算出 B(u)。"""
    global best
    fa[u] = father
    sz[u] = 1
    son[u] = 0
    for v in g[u]:
        if v == father:
            continue
        dfs1(v, u)
        sz[u] += sz[v]
        if sz[v] > sz[son[u]]:   # sz[0] 恒为 0，叶子自然没有重儿子
            son[u] = v
    # 重儿子就是最大的那个儿子，父亲方向必须等 sz[u] 完整后再算。
    balance[u] = max(sz[son[u]], n - sz[u])
    best = min(best, balance[u])


def find_centroids(root=1):
    """返回全部重心（编号升序），更新 fa、sz、son、balance、best。"""
    global best, ans
    best = n
    dfs1(root, 0)
    ans = [u for u in range(1, n + 1) if balance[u] == best]
    return ans


def centroid_on_heavy_path():
    """沿重链求重心（至多两个，编号升序），需在同一次 find_centroids 之后调用。"""
    u = 1
    while son[u] and sz[son[u]] * 2 > n:
        u = son[u]
    res = [u]
    if son[u] and sz[son[u]] * 2 == n:
        res.append(son[u])
    res.sort()
    return res

def main():
    line = sys.stdin.buffer.readline()
    if not line:
        return
    init(int(line))
    for _ in range(n - 1):
        u, v = map(int, sys.stdin.buffer.readline().split())
        add_edge(u, v)
    answer = find_centroids()
    print(len(answer))
    print(*answer)


if __name__ == "__main__":
    main()

C++
Python

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

// 树的重心（倍增跳表下降版）：把“沿重链一步步下走”压成 O(log n)。
// 约定：输入是连通无环的树，n >= 1，节点编号为 1..n。
// maxn / LOGN 按 n 的上限调整：必须保证 2^LOGN > n。
const int maxn = 300000 + 5;
const int LOGN = 20; // 2^19 = 524288 > 3e5

int n;
vector<int> g[maxn];

/*------------------------ 倍增跳表下降求重心 代码 开始 ------------------------*/
int fa[maxn];       // fa[u]：父亲，根的 fa 为 0
int sz[maxn];       // sz[u]：子树大小（含自己）
int son[maxn];      // son[u]：重儿子，叶子为 0
int up[maxn][LOGN]; // up[u][k]：沿重链从 u 向下跳 2^k 步到达的点，跳出叶子为 0
int root_node;      // build 的根，重链从这里出发
vector<int> ans;    // 重心结果，编号升序

void init(int node_count) {
    n = node_count;
    // fa / sz / son / up 会被 dfs1 与 build_jump 逐点覆写，只需清空旧图。
    for (int u = 1; u <= n; ++u) g[u].clear();
}

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 第一遍 DFS：与 hld 的 dfs1 同形，往下填 fa，回溯时汇总 sz 并选出重儿子。
// 回到 u 时 sz[u]、son[u] 都已确定，重链的第 0 层 up[u][0] 也就定了。
void dfs1(int u, int father) {
    fa[u] = father;
    sz[u] = 1;
    son[u] = 0;
    for (int v : g[u]) {
        if (v == father) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v; // sz[0] 恒为 0，叶子自然没有重儿子
    }
    up[u][0] = son[u];
}

// 第二遍：按层搭跳表。up[u][k] = up[ up[u][k-1] ][k-1]。
// 必须外层枚举 k：第 k 层只依赖第 k-1 层，这样才能保证被跳到的点已经算好。
void build_jump() {
    for (int k = 1; k < LOGN; ++k)
        for (int u = 1; u <= n; ++u)
            up[u][k] = up[up[u][k - 1]][k - 1];
}

// 预处理入口：加完边之后调用一次。root 只决定父子关系，不影响重心集合。
void build(int start = 1) {
    root_node = start;
    dfs1(root_node, 0);
    build_jump();
}

// 求“以 u 为根、大小为 sz[u] 的连通块”的全部重心（编号升序，至多两个）。
// 沿重链向下走：只要某个方向的点还不少于连通块的一半，重心必在那一侧。
// 重链上 sz 严格递减，所以“2*sz[x] >= m”沿链单调，可用跳表大步到小步贪心下降。
vector<int> centroid_of_subtree(int u) {
    int m = sz[u]; // 当前连通块的总点数
    for (int k = LOGN - 1; k >= 0; --k) {
        int v = up[u][k];
        if (v != 0 && sz[v] * 2 >= m) u = v; // 能跳就跳
    }
    ans.clear();
    ans.push_back(u); // u 的子节点方向都不足一半，它一定是重心
    if (sz[u] * 2 == m) ans.push_back(fa[u]); // 恰好一半：父节点也是重心
    sort(ans.begin(), ans.end()); // 至多两个，保证编号升序
    return ans;
}

// 整棵树的重心，就是根这一侧连通块的答案。
vector<int> centroid_all() {
    return centroid_of_subtree(root_node);
}
/*------------------------ 倍增跳表下降求重心 代码 结束 ------------------------*/

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

    int node_count;
    if (!(cin >> node_count)) return 0;
    init(node_count);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }
    build();
    vector<int> res = centroid_all();
    cout << res.size() << '\n';
    for (int i = 0; i < (int)res.size(); ++i) {
        if (i) cout << ' ';
        cout << res[i];
    }
    cout << '\n';
    return 0;
}

# 树的重心（倍增跳表下降版）：把“沿重链一步步下走”压成 O(log n)。
# 节点编号 1..n，输入必须是连通无环的树，n >= 1。
# dfs1 是递归写法，与 C++ 版同形；Python 的递归帧在堆上，
# 用 sys.setrecursionlimit() 放宽上限即可跑链形树。
import sys
from array import array

n = 0
g = []
fa = []
sz = []
son = []
up = []      # up[k][u]：沿重链从 u 向下跳 2^k 步到达的点，跳出叶子为 0
root_node = 0
ans = []


def init(node_count):
    global n, g, fa, sz, son, up, ans
    n = node_count
    # 链形树上 dfs1 会递归 n 层，先把递归上限放开。
    sys.setrecursionlimit(max(3_000_000, node_count * 4))
    g = [[] for _ in range(n + 1)]
    fa = [0] * (n + 1)
    sz = [0] * (n + 1)
    son = [0] * (n + 1)
    up = []
    ans = []


def add_edge(u, v):
    g[u].append(v)
    g[v].append(u)


def dfs1(u, father):
    """往下填 fa，回溯时汇总 sz、选出重儿子，并顺手定下跳表第 0 层。"""
    fa[u] = father
    sz[u] = 1
    son[u] = 0
    for v in g[u]:
        if v == father:
            continue
        dfs1(v, u)
        sz[u] += sz[v]
        if sz[v] > sz[son[u]]:   # sz[0] 恒为 0，叶子自然没有重儿子
            son[u] = v
    up[0][u] = son[u]


def build(start=1):
    """dfs1 求 fa / sz / son / up[0]，再按层搭跳表。root 不影响重心集合。"""
    global root_node, up
    root_node = start
    LOGN = max(1, n.bit_length())      # 2^LOGN > n
    # 用 array('i') 存跳表：每个格子 4 字节，n=3e5 时全表约 23MB，
    # 换成 list 会因为每个 int 是独立对象而涨到 150MB 以上。
    up = [array('i', bytes(4 * (n + 1))) for _ in range(LOGN)]
    dfs1(start, 0)

    # 按层搭跳表：up[k][u] = up[k-1][ up[k-1][u] ]。
    # 外层枚举 k，保证第 k 层用到第 k-1 层时已经算好。
    for k in range(1, LOGN):
        prev, cur = up[k - 1], up[k]
        for u in range(1, n + 1):
            cur[u] = prev[prev[u]]


def centroid_of_subtree(u):
    """以 u 为根、大小为 sz[u] 的连通块的全部重心（编号升序，至多两个）。"""
    global ans
    m = sz[u]                      # 当前连通块的总点数
    for k in range(len(up) - 1, -1, -1):
        v = up[k][u]
        if v and sz[v] * 2 >= m:   # 能跳就跳
            u = v
    ans = [u]                      # 子节点方向都不足一半，u 一定是重心
    if sz[u] * 2 == m:             # 恰好一半：父节点也是重心
        ans.append(fa[u])
    ans.sort()
    return ans


def centroid_all():
    """整棵树的重心，就是根这一侧连通块的答案。"""
    return centroid_of_subtree(root_node)

def main():
    line = sys.stdin.buffer.readline()
    if not line:
        return
    init(int(line))
    for _ in range(n - 1):
        u, v = map(int, sys.stdin.buffer.readline().split())
        add_edge(u, v)
    build()
    res = centroid_all()
    print(len(res))
    print(*res)


if __name__ == "__main__":
    main()

9 测试用例

9.1 两个重心

输入：

输出：

1
2

2
1 3

这就是前面的示例树，best=4。两个重心相邻，删掉它们之间的边 (1,3)，两侧恰好各有 4 个点。

9.2 单点树

输入：

输出：

1
2

1
1

此时 sz[1]=1、balance[1]=best=0，唯一的节点就是重心。

9.3 星形树

输入：

输出：

1
2

1
1

删除 1 后，每个连通块都只有 1 个点；删除任意叶子后，剩下 4 个点仍连通。因此只有 1 是重心。

9.4 链形树：验证倍增版

输入（一条 7 个点的链）：

输出：

1
2

1
4

这正是前面“倍增跳表下降”一节手算的例子。扫全树版、重链下走版、倍增跳表版四份程序输出相同。

10 重要性质

10.1 至少一个，至多两个；若有两个，必定相邻

设 c 是重心。如果删除 c 后每块都严格小于 $n/2$ ，那么对任意其他点 v，包含 c 的反方向至少有 $n-s>n/2$ 个点，所以 v 不是重心，重心唯一。

如果某一块 $C$ 恰好有 $n/2$ 个点，设其中与 c 相邻的点为 v。删除 v 后，朝 c 的块也恰好有 $n/2$ 个点，其他块更小，所以 v 也是重心。

C 中更远的点被删除后，包含 c 的块还会包含 v，其大小至少为 $n/2+1$ ，不可能是重心。其他方向的点同样不满足条件。又因为删 c 后总共只剩 $n-1$ 个点，不可能有两块同时达到 $n/2$ ，所以第二个重心至多一个。

因此，两个重心之间的边一定把树分成两个等大的部分，双重心只可能出现在偶数个节点的树中。偶数个节点并不保证有两个重心，例如 6 个节点的星形树仍只有中心节点这一个重心。

10.2 重心使到所有节点的距离和最小

定义 $F(u)=\sum_x\operatorname{dist}(u,x)$ 。切开边 (u,v) 后，设 v 一侧有 $s$ 个点。从 u 移到 v：

v 一侧的 $s$ 个点，距离各减少 1；
其余 $n-s$ 个点，距离各增加 1。

所以：

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

从 u 移到 v，左侧节点距离各加一，右侧节点距离各减一

若某个方向超过一半，向该方向移动会使距离和减小，所以非重心不可能最优。

从重心 c 出发，沿任意路径向外走，第一步前进方向的点数不超过一半；继续前进时，前方的连通块严格缩小，每一步的 $n-2s$ 都非负。因此沿任意路径距离和都不会降低，重心就是全局最优点。两个重心的距离和相同。

10.3 重心与中心的区别

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

例如链 1—2—3—4—5，再在 1 上挂四个叶子，总共 9 个点。删除 1 后最大块有 4 个点，1 是唯一重心；最长路径从一个新叶子走到 5，长 5 条边，其中间节点为 2、3，它们才是中心。

重心平衡点数，中心控制最远距离。直径中点的知识可参考 [ Rbook: 树的直径]。

10.4 重心分治为什么只有对数层

在当前大小为 $m$ 的连通块里选一个重心，删除它后，每个子问题至多有 $\lfloor m/2\rfloor$ 个点。因此沿任意递归分支，问题规模至少每层减半，递归深度为 $O(\log n)$ 。

如果每层对各连通块做线性工作，总时间为 $O(n\log n)$ ；若每层还有排序等操作，需要另算这部分开销。递归中判断重心必须使用当前连通块大小，不能一直用最初的 n。本文模板求的是一整棵树的重心，改成点分治时还需要删除标记和连通块遍历。

11 应用分类与经典例题

一、删除节点后的平衡问题

题目要求“删除一个点，使最大剩余连通块最小”，直接计算 balance。如果只要求输出最优值，输出 best；要求最小编号的重心，取 ans[0]。

二、距离和最小的选址

[ luogu P1395: 会议]

选择会议地点，使所有节点到它的距离和最小，可以先找重心，再从这个重心遍历一次，累加距离。求一个最优点及其距离和仍只需 $O(n)$ ；若题目还要求所有点的距离和，再使用上面的 $F(v)=F(u)+n-2sz[v]$ 做换根统计。

C++ 中距离和应使用 long long，因为链上距离和可达到 $O(n^2)$ 。

三、查询任意子树的重心

[ codeforces 685B: Kay and Snowflake]

这是 centroid_of_subtree(u) 最直接的应用：给一棵以 1 为根的有根树，回答 $q$ 次查询，每次问“以 $v$ 为根的子树的重心”。题目只要输出任意一个重心，所以 centroid_of_subtree 返回较深的那个就够了。

直接套模板，查询部分就是一行：

int centroid_of_subtree(int u) {   // 与上面的跳表模板完全一致
    int m = sz[u];
    for (int k = LOGN - 1; k >= 0; --k) {
        int v = up[u][k];
        if (v != 0 && sz[v] * 2 >= m) u = v;
    }
    return u;                      // 685B 只需一个重心，较深的那个即可
}

完整实现见本文前面的「倍增跳表下降版」模板（tree_centroid_jump.cpp 的 centroid_of_subtree）。预处理 $O(n\log n)$ ，每次查询 $O(\log n)$ ，总 $O((n+q)\log n)$ 。

说明

这题存在更优的 $O(n+q)$ 解法，但它用不上倍增。

自底向上递推时，可以从重儿子那里继承一个候选点：令 c = ans[heavy[u]]，然后只要 2*sz[c] < sz[u] 就让 c 沿父亲往上跳一步。因为 heavy[u] 与 u 在同一条重链上，沿同一条链自底向上走时，起点和终点的深度都单调不回溯，所以所有跳跃步数之和不超过 $n$ ——均摊 $O(n)$ 。

两种写法的方向正好相反，这是理解本题与 P5666 关系的关键：

	均摊 $O(n)$ 写法	倍增写法
起点	继承 `ans[heavy[u]]`	从 `u` 出发
方向	沿 `fa` 向上跳	沿 `heavy` 向下跳
依赖	自底向上离线递推，可继承上一条结果	不依赖任何其他查询
单次代价	均摊 $O(1)$	$O(\log n)$

685B 是离线自底向上，能复用重链上一条结果，所以不需要倍增；但一旦查询不能继承（比如删边后的补树，每次的根和大小都不同），就只能用倍增。这就是下一节 P5666 必须用跳表的原因。

四、反复拆分树上的路径问题

当需要统计经过某个分治点的路径，再分别处理剩余连通块时，选重心能控制子问题大小。这是重心分治的基础；如何统计跨子树的路径，还要由具体题目决定。

五、删边后的重心变化

[ luogu P5666: [CSP-S 2019] 树的重心]

对每条边，删除后分别处理两侧连通块的全部重心。每次重新 DFS 会达到 $O(n^2)$ ，需要进一步利用最大子树方向、换根或倍增复用信息。

这里正好是倍增跳表版的典型场景。切掉边 (p, u)（p 是 u 的父亲）后：

u 一侧是子树 u，内部结构没变，直接 centroid_of_subtree(u)， $O(\log n)$ 。
p 一侧是补树，p 的儿子集合少了 u。把 p 的重儿子换成“除 u 外最大的邻居”，改 sz[p]，重建 p 这一层的跳表，再 centroid_of_subtree(p)。

因为切边只影响 p 一个点，其余节点零修改，枚举完 $n-1$ 条边总复杂度 $O(n\log n)$ 。注意补树这一侧必须临时换根并把 sz 改成补树大小，不能用原来的 sz[p]；处理完回退现场再进入下一棵子树。

12 易错点与扩展

不要漏掉父亲方向。 即使某个点的所有儿子子树很小，n - sz[u] 仍可能很大。
比较的是整棵树的一半。 不是 sz[u] / 2，也不是 (n-1) / 2；整数判定记得包含等号。
保留全部答案。 两个重心可能同时取得最优值，题目要求最小编号时再从中选择。
DFS 根不是答案。 它只用于组织父子关系，换根不改变真实的删点结果。
区分点数和距离。 重心不是重儿子，也不一定是直径中点；度数最大同样不等于重心。
重链走法省的是扫描，不是预处理。 它跳过的是“扫全树找最小值”，sz 和 son 仍要整棵树算一遂；而且必须和同一次 build 配对。
倍增版查的是“以该点为根的子树”，不是任意连通块。 centroid_of_subtree(u) 依赖 sz[u] 恰好等于那个连通块的大小。删边后查补树一侧必须先换根并改 sz，直接传 p 会得到错误答案。
倍增版的空间是 $O(n\log n)$ 。 $n=3\times10^5$ 时 up 约占 $3\times10^5\times20\times4\text{B}\approx24\text{MB}$ ，开在全局区没有问题； $n$ 更大或要多组数据同存时要重算 LOGN。
LOGN 必须满足 $2^{LOGN}>n$ 。 否则最高的几层跳不到底，贪心会提前停下。按上限取 $\lfloor\log_2 n\rfloor+1$ 即可。

如果节点有非负权值且总权值为正，可以把“点数”替换成“点权和”，相应地统计子树权值和，并把阈值改为总权值的一半。此时需要重新检查想使用的性质：允许零权点时，满足平衡条件的点可能超过两个，不能直接照搬无权树的结论。存在负点权时，上面的平衡与距离和论证也不能直接使用。