某社区正在筹划一场义工活动,他们决定在社区内种植树木,因为树木较大,需要多人合作才能成功种植下去,现在他们已经征集到了一些志愿者,种植较大的树木时需要有一名志愿者来带领大家把树种好。
为了方便在这些志愿者中选出合适的领导者来带领大家合作种树,社区将这些志愿者(志愿者编号为1到n)以及志愿者之间的合作关系,用数据结构中的树这种结构来表示。
若当前节点有多个子树,且子树的大小都相同(子树大小是指子树中节点的数量),则该节点可以为树根,则该节点对应的志愿者可以成为领导者。
你作为本次社区活动的负责人,请编写一个程序找出所可能成为领导者的志愿者?
第一行,一个正整数 n,表示志愿者的人数。
此后n-1行,每行两个正整数u_i,v_i表示志愿者之间能合作,两两志愿者之间有且仅有一个合作关系,即图中只有一条边。
不超过 n个从小到大的整数,用空格隔开,表示每一个可能领导者的编号。
2 1 2
1 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。
云南编程挑战赛