水水的换根裸题，不过以前还真没做过换根的题

换根的思想就是在DFS中利用树的信息更新出当前点为根时的信息，具体来说一般是考虑子树外和子树内两部分

每个点的答案$ans$就是$ans[fa]+n-2*siz[nde]$

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=1000005; 6 int noww[2*N],goal[2*N]; 7 int p[N],dep[N],siz[N]; 8 int n,t1,t2,cnt,ans; 9 long long sum,maxd;10 void link(int f,int t)11 {12     noww[++cnt]=p[f];13     goal[cnt]=t,p[f]=cnt;14 }15 void DFS(int nde,int fth,int dth)16 {17     dep[nde]=dth,siz[nde]=1;18     for(int i=p[nde];i;i=noww[i])19         if(goal[i]!=fth) 20         {21             DFS(goal[i],nde,dth+1);22             siz[nde]+=siz[goal[i]];23         }24 }25 void ANS(int nde,int fth,long long las)26 {27     if(las>=maxd) ans=nde,maxd=las;28     for(int i=p[nde];i;i=noww[i])29         if(goal[i]!=fth) 30         {31             las=las+n-2*siz[goal[i]];32             ANS(goal[i],nde,las);33             las=las-n+2*siz[goal[i]];34         }35 }36 int main()37 {38     scanf("%d",&n);39     for(int i=1;i