#abc198e. [abc198_e]Unique Color
[abc198_e]Unique Color
题目描述
给定一个由 个顶点编号 到 的树。第 条边连接了顶点 和顶点 。顶点 被涂上了颜色 (在这个问题中,颜色用整数表示)。
当从顶点 到顶点 的最短路径不包含与顶点 相同颜色的顶点(除了顶点 自身)时,称顶点 是好的。
找出所有好的顶点。
约束条件
- 给定的图是一棵树。
- 输入中的所有值都是整数。
输入
输入以以下格式从标准输入中给出:
输出
按升序输出所有好的顶点,使用换行符作为分隔符。
示例输入 1
6
2 7 1 8 2 8
1 2
3 6
3 2
4 3
2 5
示例输出 1
1
2
3
4
6
例如,从顶点 到顶点 的最短路径包含顶点 。其中,只有顶点 本身被涂上了与顶点 相同的颜色,所以它是好的顶点。
另一方面,从顶点 到顶点 的最短路径包含顶点 ,并且顶点 被涂上了与顶点 相同的颜色,所以顶点 不是好的顶点。
示例输入 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