题目描述

给出一个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]的最大值即可。

#include 
     
      int n , head[1000001] , to[2000001] , next[2000001] , cnt;long long si[1000001] , f[1000001] , g[1000001];void add(int x , int y){    to[++cnt] = y;    next[cnt] = head[x];    head[x] = cnt;}void dfs1(int x , int fa){    int i;    si[x] = 1;    for(i = head[x] ; i ; i = next[i])    {        if(to[i] != fa)        {            dfs1(to[i] , x);            si[x] += si[to[i]];            f[x] += f[to[i]] + si[to[i]];        }    }}void dfs2(int x , int fa){    int i;    for(i = head[x] ; i ; i = next[i])    {        if(to[i] != fa)        {            g[to[i]] = g[x] + n - 2 * si[to[i]];            dfs2(to[i] , x);        }    }}int main(){    int i , x , y , ans = 0;    scanf("%d" , &n);    for(i = 1 ; i < n ; i ++ )        scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);    dfs1(1 , 0);    g[1] = f[1];    dfs2(1 , 0);    for(i = 1 ; i <= n ; i ++ )        if(g[ans] < g[i])            ans = i;    printf("%d\n" , ans);    return 0;}