102466: [AtCoder]ABC246 G - Game on Tree 3

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

问题描述

有一个有根树，顶点$1$为根。对于每个$i = 1, 2, \ldots, N-1$，第$i$条边连接顶点$u_i$和顶点$v_i$。除根之外的每个顶点上都写有一个正整数：对于每个$i = 2, 3, \ldots, N$，写在顶点$i$上的整数是$A_i$。Takahashi和Aoki将使用这个有根树和一个棋子来互相进行以下游戏。

棋子从顶点$1$开始。在游戏结束之前，他们重复以下过程。

1. 首先，Aoki选择一个非根顶点并将该顶点上写的整数替换为$0$。
2. 然后，Takahashi将棋子移动到棋子所在的顶点的一个（直接）子顶点。
3. 然后，如果棋子在叶顶点上，游戏结束。即使不是这种情况，Takahashi也可以选择立即结束游戏。

游戏结束时，Takahashi的分数将是棋子所在顶点上当时写的整数。Takahashi想要尽可能使他的分数最大化，而Aoki想要尽可能使其最小化。当双方都为各自的目的最优地玩时，打印Takahashi将得到的分数。

约束

• $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. Aoki将写在顶点$7$上的整数从$10$变为$0$。
3. Takahashi将棋子从顶点$1$移动到顶点$2$。
4. Aoki将写在顶点$4$上的整数从$6$变为$0$。
5. Takahashi将棋子从顶点$2$移动到顶点$5$。
6. Takahashi选择结束游戏。

游戏结束时，棋子在顶点$5$上，该顶点上写的整数为$5$，因此Takahashi的分数为$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