pku1655 Balancing Act

#include<stdio.h>
#include<vector>
using namespace std;

const int MAXN=20005;                                    
const int INF=100000000;                    
vector<int> vec[MAXN];                            
bool visit[MAXN];
int n,ans,nod;

int dfs(int x)
{
    int total=0;         //所有子树的总结点数                              
    int curMax=0;      //某一子树的结点数
    for(vector<int>::size_type i=0;i<vec[x].size();i++)
    {
        int v=vec[x][i];
        if(!visit[v])
        {
            visit[v]=true;
            int amount=dfs(v);    //返回当前访问节点的一个子树的总结点个数                

            total+=amount;        //累积该结点的所有子树的总结点个数

            if(amount>curMax)    //确定当前节点的最大的balance of node

            {
                curMax=amount;
            }
            
        }
    }

    if(n-1-total>curMax) //由于是无根树，dfs只能搜索当前节点的所有子树，对于该节点的父节点

    {                     //以及由父节点向外发散所构成的森林，可巧妙的通过做差比较

        curMax=n-1-total;
    }

    if(curMax<ans)   

    {
        ans=curMax;nod=x;
    }else if(curMax==ans&&x<nod)
    {
        nod=x;
    }

    return total+1;        //返回该节点及其所有子树所构成的森林所包含的总结点个数

}

int main()
{
    int cases;
    scanf("%d",&cases);
    while(cases--)
    {

        scanf("%d",&n);
        for(int i=0;i<=n;i++)
        {
            vec[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            int v1,v2;
            scanf("%d%d",&v1,&v2);    
            vec[v1].push_back(v2);    //无根树                        
            vec[v2].push_back(v1);
        }

        memset(visit,false,sizeof(visit));
        ans=INF;
        visit[1]=true;
        dfs(1);
        printf("%d %d\n",nod,ans);

    }        
    return 0;
}

总结：

最开始做题，确实无从下手，但现在想想，其实可以这样思考：对于树叶其值肯定是n-1，对于树枝、树根，其值就在与其相连的子树中找一个最大，这样，一个dfs的解题方案就会形成。