Game on Tree 2

AtCoder

IDabc218_g

Time2000ms

Memory256MB

Difficulty—

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. What is median?The median of a (multi-)set of $K$ numbers is defined as follows: * the $\frac{K+1}{2}$\-th smallest number, if $K$ is odd; * the average of the $\frac{K}{2}$\-th and $(\frac{K}{2}+1)$\-th smallest numbers, if $K$ is even. For example, the median of ${ 2,2,4 }$ is $2$, and the median of ${ 2,4,6,6} $ is $5$. ## Constraints * $2 \leq N \leq 10^5$ * $2 \leq A_i \leq 10^9$ * $A_i$ is even. * $1 \leq u_i < v_i \leq N$ * The given graph is a tree. * All values in input are integers. ## Input 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}$ [samples]

Samples

Input #1

Output #1

7

When both players play optimally, the game goes as follows.

*   Taro moves the piece from Vertex $1$ to Piece $5$.
*   Jiro moves the piece from Vertex $5$ to Piece $4$.
*   Taro moves the piece from Vertex $4$ to Piece $3$.
*   Jiro cannot move the piece, so the game ends.

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.

Input #2

Output #2

8

When both players play optimally, the game goes as follows.

*   Taro moves the piece from Vertex $1$ to Piece $4$.
*   Jiro cannot move the piece, so the game ends.

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.

Input #3

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

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Game on Tree 2",
    "description": {
      "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$ wr",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc218_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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$ wr...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments