树的重心

树的重心就是在一个树里，删去一个节点，使剩下的最大联通快最小。 我们要在 $O(n)$ 的时间内，求出这个重心。

如果每一个节点当根，每一个都跑一遍 dfs 的话，时间复杂度是 $O(n^2)$，显然不可以通过。

所以就要用到一个技巧：换根。 首先，我们要用 dfs 求出以 $1$ 为根的每个节点的子树大小和父节点。然后就是换根环节了，随便观察一个树以 $1$ 为根时的每个节点的子树大小，会发现：当换成 $x$ 点为根时，如果原来的根是 $fa_x$ 点，只有 $x$ 和 $fa_x$ 的子树大小会改变，而点 $x$ 的子树大小会变成 $n$，$fa_x$ 的子树大小会变成 $n-size_x$，其中 $size_i$ 表示 $i$ 的子树大小。

这个写出来之后，就只用把邻居跑一遍，满足条件的就取换根之后的 $\max$，否则直接取 $size_{ne}$。 多个重心只用求完一个重心后，每个点跑一下，如果删去这个点的重心等于已经求了的重心，就放入答案序列中。

注意点 1.在处理换根时，不可以真正的换根！！！ 只要取个 $\max$ 就行了。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[N];
int n;
int sz[N];
int fa[N];
void dfs(int u,int f){
	sz[u]=1;
	fa[u]=f;
	for(auto ne:g[u]){
		if(ne==f)continue;
		dfs(ne,u);
		sz[u]+=sz[ne];
	}
}
int k[N];
int main(){
	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);
	int ans=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		for(auto ne:g[i]){
			if(ne==fa[i])mx=max(mx,n-sz[i]);
			else mx=max(mx,sz[ne]);
		}
		if(mx<ans){
			ans=mx;
			mi=i;
		}
	}
	int t=0;
	for(int i=1;i<=n;i++){
		int mx=-1;
		for(auto ne:g[i]){
			if(ne==fa[i])mx=max(mx,n-sz[i]);
			else mx=max(mx,sz[ne]);
		}
		if(mx==ans){
			k[++t]=i;
		}
	}
	sort(k+1,k+t+1);
	for(int i=1;i<=t;i++){
		cout<<k[i]<<' ';
	}
	return 0;
}