Problem10404--洛谷P3478 - [POI2008] STA-Station

10404: 洛谷P3478 - [POI2008] STA-Station

[Creator : ]
Time Limit : 1.500 sec  Memory Limit : 512 MiB

Description

给定一个 $n$ 个点的树,请求出一个结点,使得以这个结点为根时,所有结点的深度之和最大。
一个结点的深度之定义为该节点到根的简单路径上边的数量。

Input

第一行有一个整数,表示树的结点个数 $n$。  
接下来 $(n - 1)$ 行,每行两个整数 $u, v$,表示存在一条连接 $u, v$ 的边。

Output

第一行一个整数,表示深度之和的最大值。
第二行若干个整数表示你选择的结点编号,按照升序排列。

Constraints

对于全部的测试点,保证 $1 \leq n \leq 10^6$,$1 \leq u, v \leq n$,给出的是一棵树。

Sample 1 Input

8
1 4
5 6
4 5
6 7
6 8
2 4
3 4

Sample 1 Output

28
7 8
输出 $7$ 和 $8$ 都是正确答案。

HINT

洛谷P3478.

Source/Category

换根DP 树的中心