Description

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

Input

给出一个数字N,代表有N个点.N<=1000000 下面N-1条边.

Output

输出你所找到的点,如果具有多个解,请输出编号最小的那个.

Sample Input

8

1 4

5 6

4 5

6 7

6 8

2 4

3 4

Sample Output

7

这都什么沙雕玩意儿。。

yy一下可以发现，当你计算出父亲节点的答案时，是可以O（1）继承给儿子的。。

那就乱搞

//MT_LI#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;struct node{    int x,y,next;}a[2100000];int len,last[1100000];void ins(int x,int y){    len++;    a[len].x=x;a[len].y=y;    a[len].next=last[x];last[x]=len;}int n;int dep[1100000],tot[1100000];typedef long long ll;ll f[1100000];void dfs(int x,int fa){    tot[x]=1;    for(int k=last[x];k;k=a[k].next)    {        int y=a[k].y;        if(y!=fa)        {            dep[y]=dep[x]+1;f[1]+=dep[y];            dfs(y,x);            tot[x]+=tot[y];        }    }}void dp(int x,int fa){    for(int k=last[x];k;k=a[k].next)    {        int y=a[k].y;        if(y!=fa)        {            f[y]=f[x]+n-2*tot[y];            dp(y,x);        }    }}int main(){    scanf("%d",&n);    len=0;memset(last,0,sizeof(last));    for(int i=1;i