#abc198e. [abc198_e]Unique Color

[abc198_e]Unique Color

题目描述

给定一个由 NN 个顶点编号 11NN 的树。第 ii 条边连接了顶点 AiA_i 和顶点 BiB_i。顶点 ii 被涂上了颜色 CiC_i(在这个问题中,颜色用整数表示)。

当从顶点 11 到顶点 xx 的最短路径不包含与顶点 xx 相同颜色的顶点(除了顶点 xx 自身)时,称顶点 xx好的

找出所有好的顶点。

约束条件

  • 2N1052 \leq N \leq 10^5
  • 1Ci1051 \leq C_i \leq 10^5
  • 1Ai,BiN1 \leq A_i,B_i \leq N
  • 给定的图是一棵树。
  • 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出:

NN C1CNC_1 \ldots C_N A1B1A_1 B_1 \vdots AN1BN1A_{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

例如,从顶点 11 到顶点 66 的最短路径包含顶点 1,2,3,61,2,3,6。其中,只有顶点 66 本身被涂上了与顶点 66 相同的颜色,所以它是好的顶点。
另一方面,从顶点 11 到顶点 55 的最短路径包含顶点 1,2,51,2,5,并且顶点 11 被涂上了与顶点 55 相同的颜色,所以顶点 55 不是好的顶点。

示例输入 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