{"raw_statement":[{"iden":"problem statement","content":"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.\nInitially, 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.\nTaro 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.\nWhat is median?The median of a (multi-)set of $K$ numbers is defined as follows:\n\n*   the $\\frac{K+1}{2}$\\-th smallest number, if $K$ is odd;\n*   the average of the $\\frac{K}{2}$\\-th and $(\\frac{K}{2}+1)$\\-th smallest numbers, if $K$ is even.\n\nFor example, the median of ${ 2,2,4 }$ is $2$, and the median of ${ 2,4,6,6} $ is $5$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $2 \\leq A_i \\leq 10^9$\n*   $A_i$ is even.\n*   $1 \\leq u_i < v_i \\leq N$\n*   The given graph is a tree.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"5\n2 4 6 8 10\n4 5\n3 4\n1 5\n2 4"},{"iden":"sample output 1","content":"7\n\nWhen both players play optimally, the game goes as follows.\n\n*   Taro moves the piece from Vertex $1$ to Piece $5$.\n*   Jiro moves the piece from Vertex $5$ to Piece $4$.\n*   Taro moves the piece from Vertex $4$ to Piece $3$.\n*   Jiro cannot move the piece, so the game ends.\n\nHere, 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."},{"iden":"sample input 2","content":"5\n6 4 6 10 8\n1 4\n1 2\n1 5\n1 3"},{"iden":"sample output 2","content":"8\n\nWhen both players play optimally, the game goes as follows.\n\n*   Taro moves the piece from Vertex $1$ to Piece $4$.\n*   Jiro cannot move the piece, so the game ends.\n\nHere, 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."},{"iden":"sample input 3","content":"6\n2 2 6 4 6 6\n1 2\n2 3\n4 6\n2 5\n2 6"},{"iden":"sample output 3","content":"2"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}