树的重心
时间限制: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