#P6591. [YsOI2020] 植树

    ID: 4499 远端评测题 1000ms 256MiB 尝试: 7 已通过: 4 难度: 10 上传者: 标签>O2优化枚举,暴力深度优先搜索,DFS

[YsOI2020] 植树

题目背景

Ysuperman 响应号召,决定在幼儿园里植树。

题目描述

Ysuperman 有一棵 nn 个节点的无根树 TT。如果你不知道树是什么,TA 很乐意告诉你,树是一个没有环的无向联通图。

既然树是无根的,那就没有办法种植。Ysuperman 研究了很久的园艺,发现一个节点如果可以成为根,它必须十分平衡,这意味着以它为根时,与它直接相连的节点,他们的子树大小都相同

你作为幼儿园信息组一把手,Ysuperman 给你一棵树,你能在 1s1s 内找到所有可能成为根的节点吗?

输入格式

第一行一个正整数 nn,表示树的节点个数。

此后 n1n-1 行,每行两个正整数 ui,viu_i,v_i,表示树上有一条直接连接 ui,viu_i,v_i 的边。保证每条边只会给出一次。

输出格式

不超过 nn 个从小到大的整数,用空格隔开,表示每一个可能成为根的节点。

2
1 2

1 2 
4
1 2
2 3
3 4

1 4 

9
1 2
1 3
4 1
5 1
1 6
1 9
8 1
1 7

1 2 3 4 5 6 7 8 9 

提示

样例说明

样例说明 11

11 为根时,与 11 直接相连的点有 {2}\{2\},因为只有一个所以大小全部相同。

22 为根时,与 22 直接相连的点有 {1}\{1\},因为只有一个所以大小全部相同。

所以答案为 1,21,2

样例说明 22

11 为根时,与 11 直接相连的点有 {2}\{2\},因为只有一个所以大小全部相同。

22 为根时,与 22 直接相连的点有 {1,3}\{1,3\},子树大小分别为 {1,2}\{1,2\},不相同。

33 为根时,与 33 直接相连的点有 {2,4}\{2,4\},子树大小分别为 {2,1}\{2,1\},不相同。

44 为根时,与 44 直接相连的点有 {3}\{3\},因为只有一个所以大小全部相同。

所以答案为 1,41,4


数据范围

本题采用捆绑测试。

subtask\rm{subtask} nn 分数
11 5000\le 5000 4040
22 106\le 10^6 6060

对于 100%100\% 的数据,满足 1n1061 \le n\le 10^6


提示

由于输入输出量较大,你可能需要快速输入/输出。