Unique Color

题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。顶点 $i$ 被涂成颜色 $C_i$（在本题中，颜色用整数表示）。 当从顶点 $1$ 到顶点 $x$ 的最短路径上不包含与顶点 $x$ 颜色相同的顶点（不包括顶点 $x$ 自身）时，称顶点 $x$ 为 良い（good）。 找出所有的良い顶点。

输入格式

输入从标准输入按照如下格式给出： $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

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$ 给定的图是一棵树。 输入中的所有数值均为整数。例如，从顶点 $1$ 到顶点 $6$ 的最短路径包含顶点 $1,2,3,6$。在这些顶点中，只有顶点 $6$ 本身与顶点 $6$ 颜色相同，所以它是一个良い顶点。
另一方面，从顶点 $1$ 到顶点 $5$ 的最短路径包含顶点 $1,2,5$，而顶点 $1$ 与顶点 $5$ 颜色相同，因此顶点 $5$ 不是良い顶点。

标签: AtCoder|abc198E

来源

AtCoder|abc198E