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

例如，从顶点 $1$ 到顶点 $6$ 的最短路径包含顶点 $1$，$2$，$3$，$6$。其中只有顶点 $6$ 本身与顶点 $6$ 的颜色相同，所以它是一个好的顶点。
另一方面，从顶点 $1$ 到顶点 $5$ 的最短路径包含顶点 $1$，$2$，$5$，并且顶点 $1$ 与顶点 $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