树的重心的概念

如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

说白了就是删去一个点，使这一颗树碎成的块块大小最平均的那一个点，就是重心。

树的重心的代码

我们只需要把每一个子树的大小都处理出来，在该节点的父亲方向的点可以用总量减去所有的儿子方向的子树。处理出所有子树的最大值，按照定义模拟即可。

值得注意的是，一个树可以有多个重心，但是他们一定相邻。

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

int n;
vector<int >e[10010];

int size[10010];
int g[10010];

void Input(){
	scanf("%d", &n);
	int u, v;
	for(int i=1; i<n; i++){
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
}

void Dfs(int u, int fa){
	size[u]=1;
	for(auto &p:e[u]){
		if(p==fa) continue;
		Dfs(p, u);
		size[u]+=size[p];
		g[u]=max(g[u], size[p]);
	}
	g[u]=max(g[u], n-size[u]);
}

void Work(){
	Dfs(1, 0);
	int x=1;
	for(int i=1; i<=n; i++){
		if(g[i]<g[x]) x=i;	
	}
	set<int >st;
	for(int i=1; i<=n; i++){
		if(g[i]==g[x]){
			st.insert(i);
		}
	}
	for(auto &p:st){
		printf("%d ", p);
	}
}

int main(){
	Input();
	Work();
	return 0;
}