题目描述

$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. その後、コマが葉にある場合はゲームが終了する。そうでない場合であっても、高橋君は望むならゲームを直ちに終了させることができる。

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

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

给定一棵树，有点权，B 初始在 $1$，每轮 A 选择一个点将权值变为 $0$，然后 B 移动一次，B 可在任意时刻停止游戏然后获得所在点上的权值的得分，两人均采取最优策略那么最终 B 最少会拿到多少的得分。

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

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

提示

制約

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

Sample Explanation 1

両者が最適な行動をとる場合のゲームの進行の一例として次のものがあります。 1. はじめ、コマは頂点 $1$ に置かれています。 2. 青木君が頂点 $7$ に書かれた整数を $10$ から $0$ に書き換えます。 3. 高橋君がコマを頂点 $1$ から頂点 $2$ に動かします。 4. 青木君が頂点 $4$ に書かれた整数を $6$ から $0$ に書き換えます。 5. 高橋君がコマを頂点 $2$ から頂点 $5$ に動かします。 6. 高橋君がゲームを終了します。 ゲーム終了時点でコマは頂点 $5$ にあり、頂点 $5$ にはゲーム終了時点で整数 $5$ が書かれているので、高橋君の得点は $5$ です。