题意：
给你一个由n个节点n-1条边构成的一棵树，你需要输出树的重心是那个节点，以及重心删除后得到的最大子树的节点个数size,如果size相同就选取编号最小的
题解：
树的重心定义：
找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，
生成的多棵树尽可能平衡。
洛谷中P5666树的重心 对树的重心还有这样一种描述：
一个大小为 n 的树由 nn 个结点与 n−1 条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。
对于一个大小为 n 的树与任意一个树中结点 c，称 c 是该树的重心当且仅当在树中删去 c 及与它关联的边后，分裂出的所有子树的大小均不超过 floor(n/2)（其中 floor⌊x⌋ 是向下取整函数）。对于包含至少一个结点的树，它的重心只可能有 1 或 2 个。
树的重心的性质：
1.树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
2.把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
3.把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
回归原题：
这道题我们可以随便找一个节点当作树根，然后dfs处理出来每一个节点的子节点的数量sonnum和每一个节点的子树中最大那颗子树的大小sonmax
树的定义中说过：“找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心”
那么对于一个节点x，它所有子树中最大子树节点数就是：max(sonmax[i],n-sonnum[i])
sonmax[i]：表示的是x节点的子树中最大那颗子树的大小
n-sonnum[i]：表示的是不是x的子节点的剩下所有点构成的那颗树的大小
代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define mem(a) memset(a,0,sizeof(a))
#define mem_(a) memset(a,-1,sizeof(a))
const int maxn=2e4+10;
const int INF=0x3f3f3f3f;
//链式前向星
struct node
{
int to,w,next;
}e[maxn*2]; //这个是有多少边数组就开多少
int head[maxn],cnt,sonnum[maxn],sonmax[maxn];
void add_edge(int x,int y,int z)
{
e[cnt].to=y;
e[cnt].w=z;
e[cnt].next=head[x];
head[x]=cnt++;
}
void dfs(int now,int pre)
{
sonnum[now]=1;
sonmax[now]=0;
for(int i=head[now];~i;i=e[i].next)
{
int to=e[i].to;
if(to==pre) continue;
dfs(to,now);
sonnum[now]+=sonnum[to];
sonmax[now]=max(sonmax[now],sonnum[to]);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
cnt=1;
mem_(head);
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y,0);
add_edge(y,x,0);
}
dfs(1,0);
int minn=INF,pos;
for(int i=1;i<=n;++i)
{
//根据树的重心的定义，我们发现判断一个点是不是重心 只要把这个点去掉
//看它剩下的子树结点的个数的最大值是不是最小就ok了
//子树有两种：一个是往下的即sonMax[i]，另一个是往上的 即n - sonNum[i]
//printf("%d %d***********\n",sonmax[i],n-sonnum[i]);
if(minn>max(sonmax[i],n-sonnum[i]))
{ minn=max(sonmax[i],n-sonnum[i]);
pos=i;
}
}
printf("%d %d\n",pos,minn);
}
return 0;
}