定义

  • 在一棵树中，如果选择某个结点为根，可以使得它的最大子树最小，那么这个结点就被称作这棵树的重心

性质

  1. 以重心为树根时，所有子树的大小不会超过全树大小的一半 （假设重心有一子树超过了，以这棵子树的根为新的重心即可推出矛盾）
  2. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样（假设目标点从重心往别的点偏移了一个单位，那么不少于半数的点到目标点的距离增加一个单位，不超过半数的点到目标点的距离减少一单位，易知总代价上升，故目标点就在重心处）
  3. 把两棵树通过一条边相连得到一棵新的树，那么新树的重心在连接原来两棵树重心的路径上 （与2的证明类似，假设偏移推矛盾）
  4. 在一棵树上添加或删除一个结点，那么它的重心最多只移动一条边的距离 （最多只可能是一棵子树的大小比一半多1，往该子树偏移一个单位即可，若偏移过多则会打破平衡）

求法 （DFS）

step1. 对于一个根结点u，求出每个子树的大小，加和后1记为size[u]，注意该点父结点构成的子树大小不用单独求，可直接使用 n-size[u] 求出
step2. 对于一个根结点u，标记其最大子树的大小，记为f[u]
step3. 当找到更小的f[u]时，更新重心为u，即为使得最大子树最小的结点

#注意 以上dfs过程只用进行一次，因为一次dfs即可遍历每个结点

例题

P1395 会议

题目描述

有一个村庄居住着 $n$ 个村民，有 $n-1$ 条路径使得这 $n$ 个村民的家联通，每条路径的长度都为 $1$。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

输入格式

第一行，一个数 $n$，表示有 $n$ 个村民。

接下来 $n-1$ 行，每行两个数字 $a$ 和 $b$，表示村民 $a$ 的家和村民 $b$ 的家之间存在一条路径。

输出格式

一行输出两个数字 $x$ 和 $y$。

$x$ 表示村长将会在哪个村民家中举办会议。

$y$ 表示距离之和的最小值。

输入输出样例 #1

输入 #1

1
2
3
4
4
1 2 
2 3 
3 4

输出 #1

1
2 4

说明/提示

数据范围

对于 $70%$ 数据 $n \le 10^3$。

对于 $100%$ 数据 $n \le 5 \times 10^4$。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 5;
const int INF = 0x7f7f7f7f;
int n;
vector<int> G[MAXN];
int x = 0, y = INF; 
int f[MAXN], sz[MAXN], head[MAXN], dep[MAXN];
void dfs(int u) { // 计算size[u]
    if(sz[u]) return;
    sz[u] = 1;
    for(int v : G[u]) {
        if(v == head[u]) {
            continue;
        }
        head[v] = u;
        dfs(v);
        if (sz[v] > f[u]) f[u] = sz[v];
        sz[u] += sz[v];
    }
    if(n-sz[u] > f[u]) f[u] = n-sz[u]; // u的最大子树的大小
    if(f[u] < y || (f[u]==y && u<x)) x = u, y = f[u]; // 如果最大子树较小 更新重心
}
void bfs() // 求距离之和
{
    y = 0;
    queue<int> q;
    q.push(x);
    head[x] = 0, dep[x] = 0;
    while(q.empty()==0) {
        int u = q.front();
        q.pop();
        for (int v : G[u]) {
            if(v == head[u]) continue;
            head[v] = u, dep[v] = dep[u] + 1;
            y += dep[v];
            q.push(v);
        }
    }
}
int main() {
    scanf("%d", &n);
    int a, b;
    for(int i=1; i<n; i++) {
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1); // 注意只用dfs一遍就可以遍历每个结点
    bfs();
    printf("%d %d", x, y);
    return 0;
}