5525: 领导者(leader)
Memory Limit:512 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
某社区正在筹划一场义工活动,他们决定在社区内种植树木,因为树木较大,需要多人合作才能成功种植下去,现在他们已经征集到了一些志愿者,种植较大的树木时需要有一名志愿者来带领大家把树种好。
为了方便在这些志愿者中选出合适的领导者来带领大家合作种树,社区将这些志愿者(志愿者编号为 1 到 n)以及志愿者之间的合作关系,用数据结构中的树这种结构来表示。
若当前节点有多个子树,且子树的大小都相同(子树大小是指子树中节点的数量),则该节点可以为树根,则该节点对应的志愿者可以成为领导者。
你作为本次社区活动的负责人,请编写一个程序找出所可能成为领导者的志愿者?
为了方便在这些志愿者中选出合适的领导者来带领大家合作种树,社区将这些志愿者(志愿者编号为 1 到 n)以及志愿者之间的合作关系,用数据结构中的树这种结构来表示。
若当前节点有多个子树,且子树的大小都相同(子树大小是指子树中节点的数量),则该节点可以为树根,则该节点对应的志愿者可以成为领导者。
你作为本次社区活动的负责人,请编写一个程序找出所可能成为领导者的志愿者?
Input
第一行,一个正整数 n,表示志愿者的人数。
此后 n−1 行,每行两个正整数 u_i,v_i 表示志愿者之间能合作,两两志愿者之间有且仅有一个合作关系,即图中只有一条边。
此后 n−1 行,每行两个正整数 u_i,v_i 表示志愿者之间能合作,两两志愿者之间有且仅有一个合作关系,即图中只有一条边。
Output
不超过 n 个从小到大的整数,用空格隔开,表示每一个可能领导者的编号。
Sample Input Copy
2
1 2
Sample Output Copy
1 2
HINT
对于 100% 的数据,满足 1≤n≤10^6。