F - Tree Game Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1600 点

問題文

N 頂点からなる木があり、頂点には 1 から N の番号がついています。 また、N-1 本の辺の内、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

今、各頂点 i には A_i 個の石が置いてあります。 高橋君と青木君はこの木を使ってゲームをすることにしました。

まず、高橋君が一つの頂点を選び、そこに駒を置きます。 その後、高橋君から始めて以下の操作を交互に繰り返します。

  • 今、駒がおいてある頂点から石を一つ取り除く。
  • その後、その頂点に隣接する頂点を一つ選び、そこに駒を動かす。

駒が置いてある頂点に石がなく、操作を行えない人が負けです。 高橋君がこのゲームに勝つために、最初に駒を置くことができる頂点をすべて求めてください。

制約

  • 2 ≦ N ≦ 3000
  • 1 ≦ a_i,b_i ≦ N
  • 0 ≦ A_i ≦ 10^9
  • 与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 … A_N
a_1 b_1
:
a_{N-1} b_{N-1}

出力

高橋君が最初に駒を置いて勝つことができる頂点の番号を昇順に一行に出力せよ。

入力例 1

3
1 2 3
1 2
2 3

出力例 1

2

高橋君が頂点 2 に駒を置いたとき、例えば以下のようにゲームが進みます。

  • 高橋君が駒を頂点 1 に動かす。このとき、各頂点にある石の個数は (1,1,3) である。
  • 青木君が駒を頂点 2 に動かす。このとき、各頂点にある石の個数は (0,1,3) である。
  • 高橋君が駒を頂点 1 に動かす。このとき、各頂点にある石の個数は (0,0,3) である。
  • 青木君が石を取れないため、高橋君の勝ちとなる。

入力例 2

5
5 4 1 2 3
1 2
1 3
2 4
2 5

出力例 2

1 2

入力例 3

3
1 1 1
1 2
2 3

出力例 3




題意を満たす頂点が存在しない場合があることに注意してください。






Score : 1600 points







Problem Statement
There is a tree with N vertices, numbered 1 through N.
The i-th of the N-1 edges connects vertices a_i and b_i.


Currently, there are A_i stones placed on vertex i.
Takahashi and Aoki will play a game using this tree.


First, Takahashi will select a vertex and place a piece on it.
Then, starting from Takahashi, they will alternately perform the following operation:


    

  • Remove one stone from the vertex currently occupied by the piece.
    • 

  • Then, move the piece to a vertex that is adjacent to the currently occupied vertex.
    • 



The player who is left with no stone on the vertex occupied by the piece and thus cannot perform the operation, loses the game.
Find all the vertices v such that Takahashi can place the piece on v at the beginning and win the game.











Constraints
    

  • 2 ≦ N ≦ 3000
    • 

  • 1 ≦ a_i,b_i ≦ N
    • 

  • 0 ≦ A_i ≦ 10^9
    • 

  • The given graph is a tree.
    • 

















Input
The input is given from Standard Input in the following format:


N
A_1 A_2 … A_N
a_1 b_1
:
a_{N-1} b_{N-1}












Output
Print the indices of the vertices v such that Takahashi can place the piece on v at the beginning and win the game, in a line, in ascending order.
















Sample Input 1
3
1 2 3
1 2
2 3













Sample Output 1
2




The following is one possible progress of the game when Takahashi places the piece on vertex 2:


    

  • Takahashi moves the piece to vertex 1. The number of the stones on each vertex is now: (1,1,3).
    • 

  • Aoki moves the piece to vertex 2. The number of the stones on each vertex is now: (0,1,3).
    • 

  • Takahashi moves the piece to vertex 1. The number of the stones on each vertex is now: (0,0,3).
    • 

  • Aoki cannot take a stone from the vertex, and thus Takahashi wins.
    • 















Sample Input 2
5
5 4 1 2 3
1 2
1 3
2 4
2 5













Sample Output 2
1 2
















Sample Input 3
3
1 1 1
1 2
2 3













Sample Output 3



Note that the correct output may be an empty line.