概念

  • 定义: 以这个点为根,那么所有的子树的大小都不超过整个树大小的一半。
  • 性质:
  1. 树中所有点到某个点的距离和中,到重心的距离和是最小的
  2. 把两个树通过一条边相连得到一个新的树,那么新的树的重心在连接原来两个树的重心的路径上
  3. 把一个树添加或删除一个叶子,那么它的重心最多只移动一条边的距离

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void getroot(int u,int fa=0)
{
sz[u] = 1,f[u] = 0;
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i].fi;
if(v == fa || done[v]) continue;
getroot(v,u);
sz[u] += sz[v];
f[u] = std::max(f[u],sz[v]);
}
f[u] = std::max(f[u],size - sz[u]);
if(f[u] < f[root]) root = u;
}

f[0] = size = n;
root = 0;
getroot(1);

动态维护

重心的动态维护通常用Link-Cut Tree

具体参照这篇