题目链接

传送门

Description

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大

Input

给出一个数字N,代表有N个点.N<=1000000 下面N-1条边.

Output

输出你所找到的点,如果具有多个解,请输出编号最小的那个.

Sample Input

8

1 4

5 6

4 5

6 7

6 8

2 4

3 4

Sample Output

7

题解

先用dfs把一个点做为根的时候每个点的子树大小以及深度之和算出来
然后通过自己算一算可以知道

其中to是x的子节点 size表示子树大小 dp表示深度和
这个挺好理解的
你把儿子当成父亲之后 除了儿子这棵子树的每个点深度-1之外 其他的都是+1
然后比较一下就行了

代码