题目内容

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

输入格式

给出一个数字\(N\),代表有\(N\)个点。\(N \le 1000000\)。下面\(N-1\)条边。

输出格式

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

样例输入

样例输出

思路

看到\(N \le 1000000\),只能是用\(O(N)\)的效率了。

假设当前得到的答案在结点u,要把答案转移到子结点v。

这样就会有\(n-size[v]\)的节点深度+1,\(size[v]\)的节点深度-1。

变化就是\(n-2size[v]\)的深度和。

从上向下dp。

05-11 22:14
查看更多