【题目来源】
【题目描述】
给定一颗树，树中有 n 个结点（编号1~n）。请你找到树的重心，并输出树的重心的结点编号。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中结点数的最大值最小，那么这个结点被称为树的重心。
如下图所示的树的重心为1号结点。
【输入格式】
第 1 行读入一个整数 n，代表树的结点的数量（1≤n≤10^5）；
接下来 n-1 行，每行读入两个整数 x 和 y，表示结点 x 和 y 之间有一条边（注意：不确定 x 和 y 的父子关系）。
【输出格式】
请输出树的重心的结点编号，如果树有多个重心，请按照编号从小到大依次输出，数字之间用空格隔开。
【输入样例一】
6
1 2
1 3
2 4
3 5
5 6
【输出样例一】
1 3
【输入样例二】
8
1 2
1 3
2 4
3 5
5 6
5 7
5 8
【输出样例二】
3 5
【数据范围】
1≤n≤10^5
【算法分析】
依据样例二，绘制树的示意图，然后依据定义分析“树的重心”过程如下。
删除结点 1，产生的两个连通块中结点数分别为 2、5，最大值为 5；
删除结点 2，产生的两个连通块中结点数分别为 1、6，最大值为 6；
删除结点 3，产生的两个连通块中结点数分别为 3、4，最大值为 4；
删除结点 4，产生的一个连通块中结点数分别为 7，最大值为 7；
删除结点 5，产生的四个连通块中结点数分别为 1、1、1、4，最大值为 4；
删除结点 6，产生的一个连通块中结点数分别为 7，最大值为 7；
删除结点 7，产生的一个连通块中结点数分别为 7，最大值为 7；
删除结点 8，产生的一个连通块中结点数分别为 7，最大值为 7。
综上，可知 8 个最大值中的最小值为 4，但有两个。也就是说，给出的树有两个重心，分别为结点 3、结点 5。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
const int M=N<<1;
int h[N],e[M],ne[M],idx;
int pre[N],cnt[N];
int rem[N]; //remnant
int n;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int dfs(int u,int fa) {cnt[u]=1;pre[u]=fa;for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(j!=fa) cnt[u]+=dfs(j,u);}return cnt[u];
}int main() {memset(h,-1,sizeof h);cin>>n;for(int i=1; i<n; i++) {int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1,-1);int imin=INT_MAX;for(int u=1; u<=n; u++) {rem[u]=n-cnt[u];for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(pre[j]==u) {rem[u]=max(rem[u],cnt[j]);}}imin=min(imin,rem[u]);}for(int i=1; i<=n; i++) {if(imin==rem[i]) cout<<i<<" ";}return 0;
}/*
in:
6
1 2
1 3
2 4
3 5
5 6out:
1 3
*/
【参考文献】