唯一颜色顶点

题目描述

给定一个由 $N$ 个顶点组成的树。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。顶点 $i$ 被涂上了颜色 $C_i$（在本问题中，颜色用整数表示）。

当从顶点 $1$ 到顶点 $x$ 的最短路径上，不存在除顶点 $x$ 以外与顶点 $x$ 涂有相同颜色的顶点时，称顶点 $x$ 为 好顶点。

请找出所有的好顶点。

输入格式

输入按以下格式从标准输入给出：

$N$
$C_1$ $\ldots$ $C_N$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$

输出格式

按升序以换行分隔输出所有好顶点的编号。

样例

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

1
2
3
4
6

例如，从顶点 $1$ 到顶点 $6$ 的最短路径包含顶点 $1,2,3,6$。其中除顶点 $6$ 以外，没有与顶点 $6$ 颜色相同的顶点，所以顶点 $6$ 是好顶点。

另一方面，从顶点 $1$ 到顶点 $5$ 的最短路径包含顶点 $1, 2, 5$，顶点 $1$ 与顶点 $5$ 的颜色相同，因此顶点 $5$ 不是好顶点。

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

1
2
3
5
6
7
8

数据范围

• $2 \leq N \leq 10^5$
• $1 \leq C_i \leq 10^5$
• $1 \leq A_i, B_i \leq N$
• 给定的图是树
• 输入均为整数