树的重心

参考资料

• 树的重心 - OI Wiki

简介

树的重心（centroid）是这样的节点 $v$：删去 $v$ 后，所得各连通分量的大小均不超过原树节点数的一半。重心最多有两个，且若有两个则必定相邻。

求重心用 DFS：以任意节点为根计算各子树大小 $siz_u$，每个节点 $u$ 的「重量」$mx_u=\max(siz_{child},n-siz_u)$ 即删去 $u$ 后最大连通分量的大小。$mx_u\le\lfloor n/2\rfloor$ 的节点即为重心。时间复杂度 $O(n)$。

重心的关键性质：以重心为根，任意真子树大小均不超过 $n/2$。这使得树的重心分解（点分治）成为可能。

实现

518 Bcpp

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

const int N=100005;
vector<int> G[N];
int siz[N],mx[N];
int n,ans;
void dfs(int u,int fa)
{
	siz[u]=1;mx[u]=0;
	for(auto v:G[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		siz[u]+=siz[v];
		mx[u]=max(mx[u],siz[v]);
	}
	mx[u]=max(mx[u],n-siz[u]);
	if(mx[u]<=n/2)ans=u;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	cout<<ans<<'\n';
	return 0;
}

例题

洛谷 P1364 医院设置

给定一张无向图，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小。

洛谷 P1395 会议

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