解题：POI 2008 Station

题面

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

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

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

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int noww[*N],goal[*N];

 int p[N],dep[N],siz[N];

 int n,t1,t2,cnt,ans;

 long long sum,maxd;

 void link(int f,int t)

 {

     noww[++cnt]=p[f];

     goal[cnt]=t,p[f]=cnt;

 }

 void DFS(int nde,int fth,int dth)

 {

     dep[nde]=dth,siz[nde]=;

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             DFS(goal[i],nde,dth+);

             siz[nde]+=siz[goal[i]];

         }

 }

 void ANS(int nde,int fth,long long las)

 {

     if(las>=maxd) ans=nde,maxd=las;

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             las=las+n-*siz[goal[i]];

             ANS(goal[i],nde,las);

             las=las-n+*siz[goal[i]];

         }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<n;i++)

     {

         scanf("%d%d",&t1,&t2);

         link(t1,t2),link(t2,t1);

     }

     DFS(,,);

     for(int i=;i<=n;i++) sum+=dep[i];

     ANS(,,sum); printf("%d",ans);

     return ;

 }