题目描述

$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_1$ $A_2$ $\ldots$ $A_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$

输出格式

両者が最適に行動するとき、駒が訪れた頂点に書かれた数の（多重）集合の中央値を出力せよ。

题目大意

给定一棵树，以及树各节点的点权（点权为偶数）。起初有一个棋子在树的根结点（结点 $1$）处。

• $A$ 与 $B$ 两人轮流操作：将棋子移动到其所在节点的某个叶子节点。
• 到某个节点的得分定义为：棋子经过所有结点点权的中位数。$K$ 个数的中位数定义如下：
  • 当 $K$ 为奇数时，中位数为 $K$ 个数中第 $\frac{K+1}{2}$ 小的值。
  • 当 $K$ 为偶数时，中位数为 $K$ 个数中第 $\frac{K}{2}$ 小与第 $\frac{K}{2}+1$ 小的两数的平均值。
• $A$ 希望最后得分尽可能大，$B$ 希望最后得分尽可能小。
• 当棋子到达某个叶节点时，游戏结束。

若 $A$ 先手操作，$A$，$B$ 都采取最优策略，求最终得分。

5
2 4 6 8 10
4 5
3 4
1 5
2 4

7

5
6 4 6 10 8
1 4
1 2
1 5
1 3

8

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

2

提示

制約

• $2\ \leq\ N\ \leq\ 10^5$
• $2\ \leq\ A_i\ \leq\ 10^9$
• $A_i$ は偶数
• $1\ \leq\ u_i\ <\ v_i\ \leq\ N$
• 与えられるグラフは木
• 入力は全て整数

Sample Explanation 1

両者が最適に行動するとき、ゲームは以下のように進行します。 - 太郎君が駒を頂点 $1$ から頂点 $5$ に移動させる - 次郎君が駒を頂点 $5$ から頂点 $4$ に移動させる - 太郎君が駒を頂点 $4$ から頂点 $3$ に移動させる - 次郎君は駒を動かせないのでゲームが終了する 駒が訪れた頂点に書かれた数の集合は $\{2,10,8,6\}$ となるので、中央値である $7$ を出力します。

Sample Explanation 2

両者が最適に行動するとき、ゲームは以下のように進行します。 - 太郎君が駒を頂点 $1$ から頂点 $4$ に移動させる - 次郎君は駒を動かせないのでゲームが終了する 駒が訪れた頂点に書かれた数の集合は $\{6,10\}$ となるので、中央値である $8$ を出力します。