解题：POI 2008 Station

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

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

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

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 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<n;i++)
40     {
41         scanf("%d%d",&t1,&t2);
42         link(t1,t2),link(t2,t1);
43     }
44     DFS(1,0,0);
45     for(int i=1;i<=n;i++) sum+=dep[i];
46     ANS(1,0,sum); printf("%d",ans);
47     return 0;
48 }

View Code