分数: 500 点
问题陈述
给定一棵树 N 顶点编号 1 通过 N。的 i第一条边连接顶点 A_i 和顶点 B_i。顶点 i 涂有颜色 C_i (在此问题中,颜色表示为整数)。
顶点 x 据说是 好 当从顶点开始的最短路径 1 到顶点 x 不包含与顶点颜色相同的顶点 x,顶点除外 x 本身。
找到所有好的顶点。
约束
- 2 \leq N \leq 10^5
- 1 \leq C_i \leq 10^5
- 1 \leq A_i,B_i \leq N
- 给定的图是一棵树。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
C_1 \ldots C_N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
输出
将所有好的顶点按升序打印为整数,并使用换行符作为分隔符。
示例输入 1
6 2 7 1 8 2 8 1 2 3 6 3 2 4 3 2 5
示例输出 1
1 2 3 4 6
例如,从 Vertex 出发的最短路径 1 到顶点 6 包含顶点 1,2,3,6。其中,只有Vertex 6 本身被涂成与Vertex相同的颜色 6,所以它是一个很好的顶点。
另一方面,从顶点开始的最短路径 1 到顶点 5 包含顶点 1,2,5和顶点 1 涂成与 Vertex 相同的颜色 5,所以顶点 5 不是一个好的顶点。
示例输入 2
10 3 1 4 1 5 9 2 6 5 3 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
示例输出 2
1 2 3 5 6 7 8