AT_abc218_g [ABC218G] Game on Tree 2

[problemUrl]: https://atcoder.jp/contests/abc218/tasks/abc218_g $ N $ 頂点の木があり、各頂点には $ 1 $ から $ N $ までの番号が振られています。また、$ i\,(1\ \leq\ i\ \leq\ N-1) $ 本目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでおり、頂点 $ i\,(1\ \leq\ i\ \leq\ N) $ には偶数 $ A_i $ が書かれています。太郎君と次郎君がこの木と $ 1 $ つの駒を使ってゲームをします。 はじめ、駒は頂点 $ 1 $ に置かれています。二人は太郎君から始めて交互に、駒を現在置かれている頂点と直接辺で結ばれた頂点に移動させます。ただし、駒が一度訪れた頂点に移動させることはできません。駒を移動させることができなくなった時点でゲームが終了します。 太郎君はゲームが終了するまでに駒が訪れた頂点（頂点 $ 1 $ を含む）に書かれた数の（多重）集合の中央値を最大化、次郎君は最小化したいです。両者が最適に行動するとき、駒が訪れた頂点に書かれた数の集合の中央値を求めてください。 中央値とは 大きさ $ K $ の数の（多重）集合の中央値は以下のように定義されます。 - $ K $ が奇数のとき、小さい方から $ \frac{K+1}{2} $ 番目の値 - $ K $ が偶数のとき、小さい方から $ \frac{K}{2} $ 番目の値と $ \frac{K}{2}+1 $ 番目の値の平均値 例えば、$ \{\ 2,2,4\ \} $ の中央値は $ 2 $ 、$ \{\ 2,4,6,6\} $ の中央値は $ 5 $ です。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 2\ \leq\ A_i\ \leq\ 10^9 $ - $ A_i $ は偶数 - $ 1\ \leq\ u_i\