http://www.lydsy.com/JudgeOnline/problem.php?id=1131

题意

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大

题解

感觉会爆栈，写的BFS，代码太渣了，

cost[i]记以这点为根的深度之和，sum[i]为i的子树大小。

#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000001,M=N*2;
int n,u[M],v[M],next[M],head[N],k;
int q[N],fa[N];
long long sum[N],cost[N];
 
void add(int x,int y)
{
    u[++k]=x;v[k]=y;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;next[k]=head[y];head[y]=k;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        add(x,y);
    }
    int l=0,r=1;q[1]=1;fa[1]=0;
    while(l<r)
    {
        int now=q[++l];
        for(int i=head[now];i;i=next[i])
            if(fa[now]!=v[i])
            {
                fa[v[i]]=now;
                q[++r]=v[i];
            }
    }
    for(int i=r;i>0;i--)
    {
        sum[q[i]]+=1;
        sum[fa[q[i]]]+=sum[q[i]];
        cost[fa[q[i]]]+=cost[q[i]]+sum[q[i]];
    }
    long long MAX=cost[1];int ans=1;
    for(int i=2;i<=r;i++)
    {
        cost[q[i]]=cost[fa[q[i]]]-(sum[q[i]]<<1)+n;
        if((cost[q[i]]>MAX)||(cost[q[i]]==MAX && q[i]<ans))
            MAX=cost[q[i]],ans=q[i];
    }
    printf("%d\n",ans);
}