/ Vijos / 题库 /

树的重心

树的重心

时间限制:1秒  内存限制:256M


【题目描述】

  树的重心定义为树的某个节点,当去掉该节点后,树的各个连通分量中(形成若干棵树,也就是森林),节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。

  如下图,当去掉点 1 后,树将分成两个连通块:(2,4,5),(3,6,7),则最大的连通块包含节点个数为3。若去掉点 2 ,则树将分成 3 个部分,(4),(5),(1,3,6,7)最大的连通块包含 4 个节点;第一种方法可以得到更小的最大联通分量。可以发现,其他方案不可能得到比 3 更小的值了。所以,点 1 是树的重心。
说明

【输入格式】

  第一行一个整数 \(n\),表示树的结点个数。
  接下来 \(n-1\) 行,每行两个数 \(i,j\),表示 \(i\) 和 \(j\) 有边相连。

【输出格式】

  第一行一个整数 \(K\),表示重心的个数。
  接下来 \(K\) 行,每行一个整数,表示重心。按从小到大的顺序给出。

【输入输出样例1】

 Input

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

 Output

1
1

【数据限制】

  对于 \(100\%\) 的数据,\(1≤n≤50000\)

【来源】

  Mr.he

信息

ID
2110
难度
(无)
分类
树结构 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
4
上传者