求一棵树的重心

思路：求平衡点，实际就是求一棵树的重心，我们只需要从上往下递归求出每一颗树的孩子的子树大小，模拟一个换根的过程，先把1当做根，记录下每一个节点的子树大小，在模拟换根的过程中，假设x为根，那么只需要记录一下它所有儿子的子树和以及n-其子树和中最大的值，然后取一个最小的最大值即可

#include <iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<map>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,ll>P;
const int maxn=2e4+10;
const int maxe=4e4+100;
const int inf=1e9+7;
const int mod=1e9+7;

inline int readii(){
    int sgn = 1; int cnt = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if(ch == '-')sgn = -sgn;ch = getchar();}
    while ('0' <= ch && ch <= '9') {cnt = cnt*10 + (ch-'0');ch = getchar();}
    return  sgn*cnt;
}
inline int readll(){
    int sgn = 1; int cnt = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if(ch == '-')sgn = -sgn;ch = getchar();}
    while ('0' <= ch && ch <= '9') {cnt = cnt*10 + (ch-'0');ch = getchar();}
    return  sgn*cnt;
}
int t,n;
struct edge
{
    int to;
    int val;
    int nxt;
}e[maxe];
int head[maxn],vis[maxn];
int tot_size,siz[maxn];
int tmpG,maxsz,cnt;
void Init(int x,int y)
{
    for(int i=x;i<=y;i++) head[i]=-1,vis[i]=0;
    cnt=0;tot_size=n;tmpG=0;maxsz=inf;
}
void Addedge(int u,int v,int val)
{
    e[cnt].to=v;
    e[cnt].val=val;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}
void GetG(int x)
{
    siz[x]=1;
    vis[x]=1;
    int x_max_size=0;
    for(int i=head[x];i!=-1;i=e[i].nxt)
    {
        int v=e[i].to;
        if(vis[v]) continue;
        GetG(v);
        siz[x]+=siz[v];
        x_max_size=max(x_max_size,siz[v]);
    }
    x_max_size=max(x_max_size,tot_size-siz[x]);
    if(x_max_size<maxsz)
    {
        tmpG=x;
        maxsz=x_max_size;
    }
    return ;
}
int main()
{
    while(~scanf("%d",&n))
    {
        Init(1,n);
        int u,v;
        for(int i=1;i<n;i++)
        {
            u=readii();v=readii();
            Addedge(u,v,0);
            Addedge(v,u,0);
        }
        GetG(1);
        printf("%d %d\n",tmpG,maxsz);
    }
    return 0;
}