题目描述
给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
输入
给出一个数字N,代表有N个点.N<=1000000 下面N-1条边.
输出
输出你所找到的点,如果具有多个解,请输出编号最小的那个.
样例输入
8
1 4
5 6
4 5
6 7
6 8
2 4
3 4
题解
树形dp
f[x]表示子树i中所有点到点x的距离之和。
g[x]表示整个树中所有点到点x的距离之和。
然后我们发现f和g都是可以递推求出来的，并且f[1]=g[1]。
于是可以先求f[x]，f[x]=∑(f[to[i]]+si[to[i]])。
因为这些点到x的距离比到to[i]多1，总共有si[to[i]]个点，所以加上si[to[i]]。
然后g[1]=f[1]，再递推求g[to[i]]，g[to[i]]=g[x]+n-2*si[to[i]]。
因为有n-si[to[i]]个点到to[i]的距离比到x多1，所以加n-si[to[i]]；有si[to[i]]个点到to[i]的距离比到x少1，所以再减si[to[i]]，最后就是g[x]+n-2*si[to[i]]。
最后求g[x]的最大值即可。
1 #include <cstdio> 2 int n , head[1000001] , to[2000001] , next[2000001] , cnt; 3 long long si[1000001] , f[1000001] , g[1000001]; 4 void add(int x , int y) 5 { 6 to[++cnt] = y; 7 next[cnt] = head[x]; 8 head[x] = cnt; 9 } 10 void dfs1(int x , int fa) 11 { 12 int i; 13 si[x] = 1; 14 for(i = head[x] ; i ; i = next[i]) 15 { 16 if(to[i] != fa) 17 { 18 dfs1(to[i] , x); 19 si[x] += si[to[i]]; 20 f[x] += f[to[i]] + si[to[i]]; 21 } 22 } 23 } 24 void dfs2(int x , int fa) 25 { 26 int i; 27 for(i = head[x] ; i ; i = next[i]) 28 { 29 if(to[i] != fa) 30 { 31 g[to[i]] = g[x] + n - 2 * si[to[i]]; 32 dfs2(to[i] , x); 33 } 34 } 35 } 36 int main() 37 { 38 int i , x , y , ans = 0; 39 scanf("%d" , &n); 40 for(i = 1 ; i < n ; i ++ ) 41 scanf("%d%d" , &x , &y) , add(x , y) , add(y , x); 42 dfs1(1 , 0); 43 g[1] = f[1]; 44 dfs2(1 , 0); 45 for(i = 1 ; i <= n ; i ++ ) 46 if(g[ans] < g[i]) 47 ans = i; 48 printf("%d\n" , ans); 49 return 0; 50 }
原文：http://www.cnblogs.com/GXZlegend/p/6401780.html