树的重心

参考资料

• 树的重心 - OI Wiki

思想

换根 DP：在 DFS 中计算每个子树的大小，记录「向下」的子树的最大大小，利用总点数 - 当前子树（这里的子树指有根树的子树）的大小得到「向上」的子树的大小，然后就可以依据定义找到重心了。

例题

洛谷 P1364 医院设置

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

Code (1)

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

const int inf=0x3f3f3f3f;
const int N=105;
int G[N][2];
int siz[N],f[N];
void dfs1(int u)
{
	for(auto v:G[u])
	{
		if(!v)continue;
		dfs1(v);
		siz[u]+=siz[v];
		f[1]+=siz[v];
	}
}
void dfs2(int u)
{
	for(auto v:G[u])
	{
		if(!v)continue;
		f[v]=f[u]-siz[v]*2+siz[1];
		dfs2(v);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>siz[i]>>G[i][0]>>G[i][1];
	}
	dfs1(1);
	dfs2(1);
	int ans=inf;
	for(int i=1;i<=n;i++)
	{
		ans=min(ans,f[i]);
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P1395 会议

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

Code (1)

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

using ll=long long;
const int N=1000005;
vector<int> G[N];
int fa[N],siz[N],dep[N];
ll f[N];
void dfs1(int u)
{
	siz[u]=1;
	dep[u]=dep[fa[u]]+1;
	f[1]+=dep[u]-1;
	for(auto v:G[u])
	{
		if(v==fa[u])continue;
		fa[v]=u;
		dfs1(v);
		siz[u]+=siz[v];
	}
}
void dfs2(int u)
{
	for(auto v:G[u])
	{
		if(v==fa[u])continue;
		f[v]=f[u]-siz[v]*2+siz[1];
		dfs2(v);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	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);
	}
	dfs1(1);
	dfs2(1);
	int mn=1;
	for(int i=2;i<=n;i++)
	{
		if(f[i]<f[mn])mn=i;
	}
	cout<<mn<<' '<<f[mn]<<'\n';
	return 0;
}