← 返回题目列表

AtCoder · abc198_e

E. 独特的颜色

中文机器翻译题面 查看原题

分数: 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