#11700. 树的重心

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: admin

题目描述

输入一颗树(根为1),请你求出其重心(质心)。如有多个质心,请升序输出质心序号。

样例

输入1:

4
1 2
2 3
3 4

输出1:

2 3

输入1:

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

输出1:

1

数据范围与提示

1<=n<=100000

样例1解释

质心2: 删去该质心,其最大联通分量为{3,4}, 包含节点数2个, 为所有方案中最小的

质心3: 删去该质心,其最大联通分量为{1,2}, 包含节点数也是2个, 为所有方案中最小的

样例2解释

质心1: 删去该质心,其最大联通分量有两个,分别为{2,4,5} 和 {3,6,7}, 均包含节点数3个, 为所有方案中最小的