跳转至

树的重心

定义 1：以树的重心为根时，所有子树的大小都不超过 \(\lfloor\frac{n}{2}\rfloor\)； 定义 2：树的重心是 \(\max_{v\in to[u]}{sz[v]}\) 最小的一个节点 \(u\)； 定义 3：树的重心是 \(\sum{dis(i,u)}\) 最小的一个节点 \(u\)； 定义 4：树的重心是最深的满足 \(sz[x]\ge \lceil \frac{n}{2}\rceil\) 的点；

性质 1：树的重心不超过两个，若有两个重心则二者相邻； 性质 2：重心一定在根节点所在的重链上； 性质 3（可合并性）：一条边连接两棵树，新树的重心在连接原来两棵树的重心的路径上；添加一个叶子最多让重心移动一条边；

例题

CF685B Kay and Snowflake

题目大意

给定一棵树，求出以每个点为根的子树的重心。

根据性质 2，我们可以预处理出每个节点的重儿子 \(son[u]\)，重心就位于这条重链中。

根据定义 3，可以取出 \(son[u]\) 子树的重心 \(p\)，尝试将 \(p\) 向父亲方向移动一条边，判断是否更优。

重心移动距离不超过 \(n\)，因此时间复杂度为 \(O(n)\)。

代码 
 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
#include<iostream>
using namespace std;
const int N = 3E5 + 10;

struct Edge {
    int v, next;
} pool[2 * N];
int nn, head[N];

void addEdge(int u, int v) {
    pool[++nn] = {v, head[u]};
    head[u] = nn;
}

int n, q;
int sz[N], son[N], ans[N], fa[N];

void dfs1(int u) {
    sz[u] = 1;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        fa[v] = u;
        dfs1(v);
        sz[u] += sz[v];
        if(!son[u] || sz[v] > sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u) {
    if(head[u] == 0) {
        ans[u] = u;
        return;
    }
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        dfs2(v);
    }
    ans[u] = ans[son[u]];
    while(sz[u] - sz[ans[u]] > sz[ans[u]]) ans[u] = fa[ans[u]];
}

int main() {

    cin >> n >> q;
    for(int i = 2; i <= n; i++) {
        int fa;
        cin >> fa;
        addEdge(fa, i);
    }

    dfs1(1);
    dfs2(1);

    for(int i = 1; i <= q; i++) {
        int x;
        cin >> x;
        cout << ans[x] << '\n';
    }

    return 0;
}