题目描述
给定一个n个点的无权树,求树的重心?
重心定义为,在所有点中,删去该点之后,树中的所有子树的包含节点个数最多的那个子树包含节点个数最小。
具体根据样例推一下
输入格式
第一行一个n。
接下来n-1行,每行分别有两个数a和b,表示节点a到节点b有一条无向边。
输出格式
求这棵树的重心(保证唯一)
样例数据
input
10
1 2
1 3
3 4
1 5
1 6
3 7
1 8
1 9
9 10
output
1
数据规模与约定
保证$ n \leq 10^5$。
给定一个n个点的无权树,求树的重心?
重心定义为,在所有点中,删去该点之后,树中的所有子树的包含节点个数最多的那个子树包含节点个数最小。
具体根据样例推一下
第一行一个n。
接下来n-1行,每行分别有两个数a和b,表示节点a到节点b有一条无向边。
求这棵树的重心(保证唯一)
input
10
1 2
1 3
3 4
1 5
1 6
3 7
1 8
1 9
9 10
output
1
保证$ n \leq 10^5$。