小G有一个大树-题解

题目描述
小G想要把自己家院子里的橘子树搬到家门口（QAQ。。就当小G是大力水手吧）
可是小G是个平衡性灰常灰常差的人，他想找到一个这个橘子树的平衡点。
怎么描述这棵树呢。。。就把它看成由一个个节点构成的树吧。结点数就
代表树重。

输入描述:
多组数据输入输出，
第一行包含一个整数n（3<=n<=1000）代表树的结点的个数
以下n-1行描述（1-n）节点间的连接关系。
思路：找树的重心，就是找到节点的最大子树子树最小的点。
代码：

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

int sonnum[1005];
vector<int>edge[1005];
int ansid,anssum=0x3f3f3f3f,n;
void dfs(int u,int pre)
{
    int maxnum=0;
    sonnum[u]=1;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(v==pre)continue;
        dfs(v,u);
        sonnum[u]+=sonnum[v];
        if(sonnum[v]>maxnum)maxnum=sonnum[v];
    }
    maxnum=max(maxnum,n-sonnum[u]);
    if(maxnum<anssum){
        ansid=u;
        anssum=maxnum;
    }else if(maxnum==anssum&&u<ansid){
        ansid=u;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1,-1);
    printf("%d %d\n",ansid,anssum);
    return 0;
}