切割树--中级

 1 Sec 64 MB |  显示标签
1940
通过提交

题目描述

有一个N个节点的无根树,各节点编号为1..N,现在要求你删除其中的一个点,使分割开的连通块中节点个数都不超过原来的一半多。
1 <= N <= 10,000

输入格式

第一行:一个整数N。
后面有N-1行:每行两个整数 X 和 Y,表示一个边连接的两个节点号。

输出格式

输出所有可能选择的点。如果有多个节点,按编号从小到大输出,每个一行。 如果找不到这样的点,输出一行:"NONE".

样例输入 #1

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

样例输出 #1

3
8 

提示

【样例说明】删除3号或8号节点,则分枝最多有5个节点

 上传者
coach
 创建时间
2013-07-25 21:23