Competitions
Trees: Depth First Search
Unique Color
Given a tree with n vertices numbered 1 through n. The i-th edge connects Vertex ai
and Vertex bi
. Vertex i is painted in color ci
(in this problem, colors are represented as integers).
Vertex x is said to be good when the shortest path from Vertex 1 to Vertex x does not contain a vertex painted in the same color as Vertex x, except Vertex x itself.
Find all good vertices.
Input
The first line contains number of vertices n (2 ≤ n ≤ 105
). The second line contains colors c1
, c2
, ..., cn
(1 ≤ ci
≤ 105
). Each of the next n - 1 lines contains two integers ai
and bi
(1 ≤ ai
, bi
≤ n).
Output
Print all good vertices as integers, in ascending order. Print each number in a separate line.
Input example #1
6 2 7 1 8 2 8 1 2 3 6 3 2 4 3 2 5
Output example #1
1 2 3 4 6
Input example #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
Output example #2
1 2 3 5 6 7 8