AT_agc010_f [AGC010F] Tree Game

[problemUrl]: https://atcoder.jp/contests/agc010/tasks/agc010_f $ N $ 頂点からなる木があり、頂点には $ 1 $ から $ N $ の番号がついています。 また、$ N-1 $ 本の辺の内、$ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 今、各頂点 $ i $ には $ A_i $ 個の石が置いてあります。 高橋君と青木君はこの木を使ってゲームをすることにしました。 まず、高橋君が一つの頂点を選び、そこに駒を置きます。 その後、高橋君から始めて以下の操作を交互に繰り返します。 - 今、駒がおいてある頂点から石を一つ取り除く。 - その後、その頂点に隣接する頂点を一つ選び、そこに駒を動かす。 駒が置いてある頂点に石がなく、操作を行えない人が負けです。 高橋君がこのゲームに勝つために、最初に駒を置くことができる頂点をすべて求めてください。

N/A

N/A

### 制約 - $ 2\ ≦\ N\ ≦\ 3000 $ - $ 1\ ≦\ a_i,b_i\ ≦\ N $ - $ 0\ ≦\ A_i\ ≦\ 10^9 $ - 与えられるグラフは木である。 ### Sample Explanation 1 高橋君が頂点 $ 2 $ に駒を置いたとき、例えば以下のようにゲームが進みます。 - 高橋君が駒を頂点 $ 1 $ に動かす。このとき、各頂点にある石の個数は $ (1,1,3) $ である。 - 青木君が駒を頂点 $ 2 $ に動かす。このとき、各頂点にある石の個数は $ (0,1,3) $ である。 - 高橋君が駒を頂点 $ 1 $ に動かす。このとき、各頂点にある石の個数は $ (0,0,3) $ である。 - 青木君が石を取れないため、高橋君の勝ちとなる。 ### Sample Explanation 3 題意を満たす頂点が存在しない場合があることに注意してください。