配点 : $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}$

出力

答えを出力せよ。

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

5

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

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

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

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

70