来源：牛客网
：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

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

输入描述:

多组数据输入输出， 第一行包含一个整数n（3<=n<=1000）代表树的结点的个数 以下n-1行描述（1-n）节点间的连接关系。 输出描述:
输出两个个整数 x，num 分别代表树的平衡点，和删除平衡点后最大子树的结点数（如果结点数相同输出编号小的）。

示例1
输入
复制

3
1 2
1 3

输出
复制

1 1

题解：

树型dp入门
状态转移方程：dp[i]=max(n-tot[i],max(tot[k]))
dp[x]:表示以x为根的树的节点数
在dfs过程中把状态转移方程带进去

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
vector<int>edge[maxn];
int num,ans;
int dp[maxn];
int n;
void dfs(int u,int fa)
{
    dp[u]=1;
    int maxx=0;
    for(int i=0;i<edge[u].size();i++)
    {
        int v=edge[u][i];
        if(v==fa)continue;
        dfs(v,u);
        dp[u]+=dp[v];//v是u的子树 
        maxx=max(dp[v],maxx);
    }
    maxx=max(maxx,n-dp[u]);//判断是这个子树重，还是另一个 
    // dp[i]=max(n-tot[i],max(tot[k])) 树形dp 
    if(maxx<num)//删除平衡点后最大子树的结点数
    {
        num=maxx;
        ans=u; 
    }
    else if(maxx==num)
    {
        if(ans>u)ans=u;//如果结点数相同，我们要编号更小的 
     } 
}
int main()
{

    while(cin>>n)
    {
        num=ans=0x7f;
        for(int i=1;i<=n;i++)
        {
            edge[i].clear();
            dp[i]=0;
        }
        for(int i=1;i<n;i++)
        {
            int u,v;
            cin>>u>>v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        dfs(1,0);
        cout<<ans<<" "<<num<<endl;
    }
}