G - Game on Tree 3 Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 個の頂点を持ち、頂点 1 を根とする根付き木があります。 i = 1, 2, \ldots, N-1 について、i 本目の辺は頂点 u_i と頂点 v_i を結びます。 また、根以外の頂点には正の整数が書かれており、具体的には、i = 2, 3, \ldots, N について、頂点 i に正の整数 A_i が書かれています。 高橋君と青木君はこの根付き木と 1 個のコマを使って次の対戦ゲームをします。

はじめ、頂点 1 にコマが置かれています。その後、ゲームが終了するまで下記の手順を繰り返します。

  1. まず、青木君が根以外の頂点を任意に 1 個選び、その頂点に書かれた整数を 0 に書き換える。
  2. 次に、高橋君がコマを、いまコマがある頂点の（直接の）子のいずれかに移動する。
  3. その後、コマが葉にある場合はゲームが終了する。そうでない場合であっても、高橋君は望むならゲームを直ちに終了させることができる。

ゲーム終了時点でコマがある頂点に、ゲーム終了時点で書かれている整数が、高橋君の得点となります。 高橋君は自身の得点を出来るだけ大きく、青木君は高橋君の得点を出来るだけ小さくしたいです。 両者がそのために最適な行動を取るときの高橋君の得点を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq u_i, v_i \leq N
  • 与えられるグラフは木である。
  • 入力はすべて整数

入力

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

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

出力

答えを出力せよ。

入力例 1

7
2 4 6 5 6 10
1 2
1 3
2 4
2 5
5 6
5 7

出力例 1

5

両者が最適な行動をとる場合のゲームの進行の一例として次のものがあります。

  1. はじめ、コマは頂点 1 に置かれています。
  2. 青木君が頂点 7 に書かれた整数を 10 から 0 に書き換えます。
  3. 高橋君がコマを頂点 1 から頂点 2 に動かします。
  4. 青木君が頂点 4 に書かれた整数を 6 から 0 に書き換えます。
  5. 高橋君がコマを頂点 2 から頂点 5 に動かします。
  6. 高橋君がゲームを終了します。

ゲーム終了時点でコマは頂点 5 にあり、頂点 5 にはゲーム終了時点で整数 5 が書かれているので、高橋君の得点は 5 です。

入力例 2

30
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 32 38 84 49 93 53 26 13 25
13 15
14 22
17 24
12 3
4 3
5 8
26 15
3 2
2 9
4 25
4 13
2 10
28 15
6 4
2 5
19 9
2 7
2 14
23 30
17 2
7 16
21 13
13 23
13 20
1 2
6 18
27 6
21 29
11 8

出力例 2

70

Score : 600 points

Problem Statement

There is a rooted tree with N vertices, Vertex 1 being the root. For each i = 1, 2, \ldots, N-1, the i-th edge connects Vertex u_i and Vertex v_i. Each vertex other than the root has a positive integer written on it: for each i = 2, 3, \ldots, N, the integer written on Vertex i is A_i. Takahashi and Aoki will use this rooted tree and a piece to play the following game against each other.

The piece starts on Vertex 1. Until the game ends, they repeat the following procedure.

  1. First, Aoki chooses a non-root vertex and replaces the integer written on that vertex with 0.
  2. Next, Takahashi moves the piece to a (direct) child of the vertex the piece is on.
  3. Then, the game ends if the piece is on a leaf. Even if that is not the case, Takahashi can choose to end the game immediately.

At the end of the game, Takahashi's score will be the integer written at that time on the vertex the piece is on. Takahashi wants to make his score as large as possible, while Aoki wants to make it as small as possible. Print the score Takahashi will get when both players play optimally for their respective purposes.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 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_2 \ldots A_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Print the answer.

Sample Input 1

7
2 4 6 5 6 10
1 2
1 3
2 4
2 5
5 6
5 7

Sample Output 1

5

Here is a possible progression of the game when both players play optimally.

  1. The piece starts on Vertex 1.
  2. Aoki changes the integer written on Vertex 7 from 10 to 0.
  3. Takahashi moves the piece from Vertex 1 to Vertex 2.
  4. Aoki changes the integer written on Vertex 4 from 6 to 0.
  5. Takahashi moves the piece from Vertex 2 to Vertex 5.
  6. Takahashi chooses to end the game.

At the end of the game, the piece is on Vertex 5, on which the integer 5 is written at that time, so Takahashi's score will be 5.

Sample Input 2

30
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 32 38 84 49 93 53 26 13 25
13 15
14 22
17 24
12 3
4 3
5 8
26 15
3 2
2 9
4 25
4 13
2 10
28 15
6 4
2 5
19 9
2 7
2 14
23 30
17 2
7 16
21 13
13 23
13 20
1 2
6 18
27 6
21 29
11 8

Sample Output 2

70