• Source 
    1. /**************************************************************
    2.     Problem: 1131
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:8428 ms
    7.     Memory:130688 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. //by zrt
    14. //problem:
    15. using namespace std;
    16. typedef long long ll;
    17. const double eps(1e-10);
    18. /*
    19. Sub(x) = sigma Sub(childk) + 1
    20. Down(x) = sigma Down(childk) + Sub(x)
    21. Up(x) = Up(Fa(x)) + Down(Fa(x)) ?Down(x) ?Sub(x) + N ?Sub(x)
    22.  
    23. */
    24. int n;
    25. int H[1000005],P[2000005],X[2000005],tot;
    26. inline void add(int x,int y){
    27.     P[++tot]=y,X[tot]=H[x],H[x]=tot;
    28. }
    29. long long son[1000005],down[1000005],up[1000005],fa[1000005];
    30. int stk[20000050],top;
    31. bool vis[1000005];
    32. int main(){
    33.     #ifdef LOCAL
    34.     freopen("in.txt","r",stdin);
    35.     freopen("out.txt","w",stdout);
    36.     #endif
    37.     tot=1;
    38.     scanf("%d",&n);
    39.     for(int i=1,x,y;i<n;i++){
    40.         scanf("%d%d",&x,&y);
    41.         add(x,y);add(y,x);
    42.     }
    43.     stk[top++]=1;
    44.     int x;
    45.     while(top>0){
    46.         x=stk[--top];
    47.         if(!vis[x]){
    48.             vis[x]=1;
    49.             stk[top++]=x;
    50.             for(int i=H[x];i;i=X[i]){
    51.                 if(P[i]==fa[x]) continue;
    52.                 fa[P[i]]=x;
    53.                 stk[top++]=P[i];
    54.             }
    55.         }else{
    56.             for(int i=H[x];i;i=X[i]){
    57.                 if(P[i]==fa[x]) continue;
    58.                 son[x]+=son[P[i]];
    59.                 down[x]+=down[P[i]];
    60.             }
    61.             son[x]+=1;
    62.             down[x]+=son[x];
    63.         }
    64.     }
    65.     stk[top++]=1;
    66.     while(top>0){
    67.         x=stk[--top];
    68.         if(fa[x]!=0) up[x]=up[fa[x]]+down[fa[x]]-down[x]-son[x]+n-son[x];
    69.         for(int i=H[x];i;i=X[i]){
    70.             if(P[i]==fa[x]) continue;
    71.             stk[top++]=P[i];
    72.         }
    73.     }
    74.     long long maxn=-1;int maxx;
    75.     for(int i=1;i<=n;i++){
    76.         if(up[i]+down[i]>maxn){
    77.             maxn=up[i]+down[i];
    78.             maxx=i;
    79.         }
    80.     }
    81.     printf("%d\n",maxx);
    82.     return 0;
    83. }