Score : $600$ points
We have a tree with $N$ vertices numbered $1$ through $N$. The $i$-th edge $(1 \leq i \leq N-1)$ connects Vertex $u_i$ and Vertex $v_i$, and Vertex $i$ $(1 \leq i \leq N)$ has an even number $A_i$ written on it. Taro and Jiro will play a game using this tree and a piece.
Initially, the piece is on Vertex $1$. With Taro going first, the players alternately move the piece to a vertex directly connected to the vertex on which the piece lies. However, the piece must not revisit a vertex it has already visited. The game ends when the piece gets unable to move.
Taro wants to maximize the median of the (multi-)set of numbers written on the vertices visited by the piece before the end of the game (including Vertex $1$), and Jiro wants to minimize this value. Find the median of this set when both players play optimally.
The median of a (multi-)set of $K$ numbers is defined as follows:
Input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$
Print the median of the (multi-)set of numbers written on the vertices visited by the piece when both players play optimally.
5 2 4 6 8 10 4 5 3 4 1 5 2 4
7
When both players play optimally, the game goes as follows.
Here, the set of numbers written on the vertices visited by the piece is $\{2,10,8,6\}$. The median of this set is $7$, which should be printed.
5 6 4 6 10 8 1 4 1 2 1 5 1 3
8
When both players play optimally, the game goes as follows.
Here, the set of numbers written on the vertices visited by the piece is $\{6,10\}$. The median of this set is $8$, which should be printed.
6 2 2 6 4 6 6 1 2 2 3 4 6 2 5 2 6
2