切割树--中级
1 Sec 64 MB |
19 | 40 |
通过 | 提交 |
题目描述
有一个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个节点