G - Game on Tree 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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 です。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

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

入力例 1

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

出力例 1

7

両者が最適に行動するとき、ゲームは以下のように進行します。

  • 太郎君が駒を頂点 1 から頂点 5 に移動させる
  • 次郎君が駒を頂点 5 から頂点 4 に移動させる
  • 太郎君が駒を頂点 4 から頂点 3 に移動させる
  • 次郎君は駒を動かせないのでゲームが終了する

駒が訪れた頂点に書かれた数の集合は \{2,10,8,6\} となるので、中央値である 7 を出力します。

入力例 2

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

出力例 2

8

両者が最適に行動するとき、ゲームは以下のように進行します。

  • 太郎君が駒を頂点 1 から頂点 4 に移動させる
  • 次郎君は駒を動かせないのでゲームが終了する

駒が訪れた頂点に書かれた数の集合は \{6,10\} となるので、中央値である 8 を出力します。

入力例 3

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

出力例 3

2

Score : 600 points

Problem Statement

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}

Output

Print the median of the (multi-)set of numbers written on the vertices visited by the piece when both players play optimally.

Sample Input 1

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

Sample 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.

Sample Input 2

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

Sample 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.

Sample Input 3

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

Sample Output 3

2