这是找树的重心的经典题目。
树的重心有下面几条常见性质：
定义1：找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心。
定义2：以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。
性质1：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
性质2：把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
性质3：把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
方法：就记节点1为树的根，两次dfs，第一次求出每个节点的所有子孙再加上它自己的节点总数num[i]。第二次就算出每个节点的balance值bal[i]，算的时候就比较节点i它所有子节点的num值（删掉它之后以每个它的子节点为根形成一棵新树）还有n-num[i]的值（删掉i之后它的父节点及其相关节点也形成一棵新树），最大的就是bal[i]。
注意：WA了几次是因为没有考虑边界情况（n==2），dfs写的太不熟练了，代码能力有待提高啊！
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
#define INF 1000000000
#define eps 1e-8
#define pii pair<int,int>
#define LL long long int
int T,n,a,b,ans_i,ans;
vector<int>v[];
int num[],bal[];
int dfs1(int i,int fa);
void dfs2(int i,int fa);
int main()
{
//freopen("in2.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&T);
while(T--)
{
ans_i=;
ans=INF;
scanf("%d",&n);
if(n==)
{
printf("1 0\n");
}
else if(n==)
{
scanf("%d%d",&a,&b);
printf("1 1\n");
}
else
{
for(int i=; i<=n; i++)
{
v[i].clear();
num[i]=;
bal[i]=-;
}
for(int i=; i<n; i++)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs1(,-);
dfs2(,-);
for(int i=; i<=n; i++)
{
if(bal[i]<ans)
{
ans_i=i;
ans=bal[i];
}
}
printf("%d %d\n",ans_i,ans);
}
}
//fclose(stdin);
//fclose(stdout);
return ;
}
int dfs1(int i,int fa)
{
/*if(v[i].size()==1)
return num[i];*/
/*这句判断是不能加的，加了就是WA，个中原因非常微妙：
因为我加这句的本意是当遇到了叶子节点时，它的num就直接返回1就行了，
而叶节点的size就是1（只有父节点）。
但是我这里就忽略了一种特殊情况，那就是这棵数可能根节点的size也为1！！！
所以就在这种情况下WA了。
实际上没有必要加这一句，下面的循环语句已经可以很好的处理各个节点了。*/
//这里可以总结一条树的性质：叶节点一定含一条边，根节点可能含一条边，其它节点至少含两条边。
for(unsigned int j=; j<v[i].size(); j++)
{
int &t=v[i][j];
if(t==fa)
{
continue;
}
else
{
num[i]+=dfs1(t,i);
}
}
//cout<<i<<"_-_"<<num[i]<<endl;
return num[i];
}
void dfs2(int i,int fa)
{
for(unsigned int j=; j<v[i].size(); j++)
{
int &t=v[i][j];
if(t==fa)
{
bal[i]=max(bal[i],num[]-num[i]);
}
else
{
bal[i]=max(bal[i],num[t]);
dfs2(t,i);
}
}
//cout<<i<<"___"<<bal[i]<<endl;
}
后来看了其它人的题解发现其实这两次的dfs结构差不多，写一次dfs就足够了，减少代码量。而且只要求最小bal，不用每个点的bal都保存，这样可以节省空间。还有一个小技巧，就是我这是从根节点遍历树，我没有必要用一个标记数组uesd[maxn]来记录每个点是不是遍历过了，只要判断每次是不是父节点就行了，父节点肯定遍历过，子节点肯定没遍历过。这样就用节省空间了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
#define INF 1000000000
#define eps 1e-8
#define pii pair<int,int>
#define LL long long int
const int maxn=;
int T,n,a,b,head[maxn],cnt,ansi,ansb;
struct node
{
int v,next;
}e[maxn<<];/*前向星存图时这个结构体数组存的是边的信息，
如果是无向图，千万注意要开二倍！这里容易错。*/
void ini()
{
memset(head,-,sizeof(int)*(n+));
cnt=;
ansi=ansb=INF;
}
void add(int aa,int bb)
{
e[cnt].v=bb;
e[cnt].next=head[aa];
head[aa]=cnt++;
}
int dfs(int x,int fa)
{
int sum=,bx=,t;
//sum是以当前的x节点为根的子树所包含的节点数
//bx是x节点的平衡值
for(int i=head[x];i!=-;i=e[i].next)
{
if(e[i].v==fa) continue;/*使用前向星存图在遍历每个点的边时要注意i是边的标号而
不是点的标号，这里不能误写成i==fa*/
else
{
t=dfs(e[i].v,x);
bx=max(bx,t);//用子树的节点数更新bx
sum+=t;
}
}
bx=max(n-sum,bx);//这一步不能少
if((bx<ansb)||(bx==ansb&&ansi>x))
{
ansi=x;
ansb=bx;
}
return sum;
}
int main()
{
//freopen("in6.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ini();
for(int i=;i<=n-;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(,-);
printf("%d %d\n",ansi,ansb);
}
return ;
}