UOJ Logo 蜗牛编程训练题库

JZOJ

#503. 树形dp练习3

Statistics
时间限制:1s    空间限制:256MB    输入文件:T3.in    输出文件:T3.out
当前24小时内您还剩30次提交本题的机会

题目描述

给定一个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$。

Solutions

标题 发表者 发表日期
None