P26025

领导者

难度 未定 图论算法 树上问题
讨论 统计 6通过 17提交 35.3%通过率 旧版界面
时间限制 1 秒 内存限制 512 MB

题目描述

某社区正在筹划一场义工活动,他们决定在社区内种植树木,因为树木较大,需要多人合作才能成功种植下去,现在他们已经征集到了一些志愿者,种植较大的树木时需要有一名志愿者来带领大家把树种好。
为了方便在这些志愿者中选出合适的领导者来带领大家合作种树,社区将这些志愿者(志愿者编号为1到n)以及志愿者之间的合作关系,用数据结构中的树这种结构来表示。
若当前节点有多个子树,且子树的大小都相同(子树大小是指子树中节点的数量),则该节点可以为树根,则该节点对应的志愿者可以成为领导者。
你作为本次社区活动的负责人,请编写一个程序找出所可能成为领导者的志愿者?

输入

第一行,一个正整数 n,表示志愿者的人数。
此后n-1行,每行两个正整数u_i,v_i表示志愿者之间能合作,两两志愿者之间有且仅有一个合作关系,即图中只有一条边。

输出

不超过 n个从小到大的整数,用空格隔开,表示每一个可能领导者的编号。

样例

样例 1
输入
2
1 2
输出
1 2
样例 2
输入
4
1 2
2 3
3 4
输出
1 4

提示

【样例2解释】

以 1为领导时,与 1直接合作的志愿者有 {2},因为只有一个直接合作的志愿者,所以大小全部相同。
以 2 为领导时,与 2直接合作的志愿者有 {1,3},间接志愿者人数分别为 {1,2},不相同。
以 3为领导时,与 3直接合作的志愿者有 {2,4},间接志愿者人数分别为 {2,1},不相同。
以 4为领导时,与 4直接合作的志愿者有 {3},因为只有一个直接合作的志愿者,所以大小全部相同。所以答案为 1,4。
【数据范围】

对于 100%的数据,满足 1≤n≤10^6。

来源

云南编程挑战赛

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交