求一棵树任意子树的重心

（2022.11.21 重写）

定义

设 $\newcommand\siz{\operatorname{siz}}\newcommand\hson{\operatorname{hson}}\siz(x)$ 表示 $x$ 的子树大小（含 $x$），$\hson(x)$ 表示 $x$ 的重儿子。将边 $(x,\hson(x))$ 称为一条重边，其余不满足该条件的边称为轻边；将相邻的重边两两相连形成的链称为重链。

命题

一棵以 $\newcommand\rt{\text{rt}}\rt$ 为根的树，其重心 $c$ 满足以下条件：

• $c$ 在以 $\rt$ 为顶的重链上；$(1)$
• $c$ 的所有祖先（记其中一个为 $x$），均满足 $\siz(\hson(x))>\frac{\siz(rt)}{2}$；$(2)$
• $\siz(\hson(c))\leq \frac{\siz(rt)}{2}$。$(3)$

证明

记 $n=\siz(\rt)$。考虑任意节点 $x$。不难发现若 $y\neq \hson(x)$，则 $\siz(y)<\frac{\siz(x)}{2}$，又 $\siz(x)\leq n$，进而 $\siz(y)<\frac{n}{2}$，则 $n-\siz(y)>\frac{n}{2}$。换句话说，以 $y$ 子树中任意节点为根，在其祖先方向上的所有节点数量已超过全树一半，不可能成为重心。考虑从 $x=\rt$ 开始反复应用以上结论，$(1)$ 即得证。

对于 $(2)$ 和 $(3)$，我们考虑归纳法。对于 $x=\rt$，结论显然成立；假如现在处于节点 $x$，它位于 $\rt$ 为顶的重链上，且其所有祖先均满足 $(2)$。则有 $n-\siz(x)\leq\frac{n}{2}$。若有 $\siz(\hson(x))\leq\frac{n}{2}$，则其轻儿子的大小亦然。根据定义，它显然为整棵树的重心；否则由 $(3)$ 可以得到应向 $\hson(x)$ 探查，同时由 $\siz(\hson(x))>\frac{n}{2}$ 继续保证了 $n-\siz(\hson(x))\leq\frac{n}{2}$。$\square$

应用

CF685B – Kay and Snowflake

本题要你求取一棵树以 $x$ 为根的子树的任意一个重心。我们将该树作轻重链剖分。对于每条重链，我们开设顺序存储数据结构保存其每一节点的重儿子大小。易知该序列是单减的。在上面二分找到首个满足条件的节点即可。或者直接从底向上依次求取每个子树的重心，则答案单调“上移”（深度不增），优化复杂度到线性。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 327680;
int n, x, y, q, head[N], e_cnt, lim;
int f[N], h_son[N], centroid[N], father[N]; // f[i]是以i为根的子树的节点数；h_son[i]是i的重儿子。 
int ans[N];
struct edge {
	int v, nxt;
} e[N << 1];

void add_e (int x, int y) {
	e[++e_cnt].nxt = head[x], head[x] = e_cnt, e[e_cnt].v = y;
}

void dfs (int x, int fr) {
	f[x] = 1, father[x] = fr, centroid[x] = x; // 叶子节点的重心是它自己
	for (int i = head[x]; i; i = e[i].nxt) {
		dfs (e[i].v, x);
		f[x] += f[e[i].v];
		if (f[e[i].v] > f[h_son[x]]) // 更新重儿子信息 
			h_son[x] = e[i].v;
	}
	if (!h_son[x]) return;
	int cent = centroid[h_son[x]];
	while (cent != x) {
		if (f[x] - f[cent] <= (f[x] >> 1) && f[h_son[cent]] <= (f[x] >> 1)) { // 判断是否能成为重心 
			centroid[x] = cent;
			break;
		}
		cent = father[cent];
	}
}

int main () {
	/* CF685B / hwhw-树形DP（树的直径和重心） G - Kay and Snowflake 吴秋实 */
	scanf ("%d%d", &n, &q);
	for (int i = 2; i <= n; ++i) {
		scanf ("%d", &y);
		add_e (y, i);
	}
	dfs (1, 0);
	for (int i = 1; i <= q; ++i) {
		scanf ("%d", &x);
		printf ("%d\n", centroid[x]);
	}

	return 0;
}