配点 : $1600$ 点

問題文

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

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

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

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

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

制約

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

入力

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

$N$

$A_1$ $A_2$ … $A_N$

$a_1$ $b_1$

:

$a_{N-1}$ $b_{N-1}$

出力

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

3
1 2 3
1 2
2 3

2

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

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

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

1 2

3
1 1 1
1 2
2 3

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