树上的游戏 3

题目描述

有一棵以顶点 $1$ 为根的、具有 $N$ 个顶点的有根树。 对每个 $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 将获得的得分。

输入格式

输入按以下格式从标准输入给出:

N
A_2 … A_N
u_1 v_1
u_2 v_2
⋮
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$。

Aoki 把写在顶点 $7$ 上的整数从 $10$ 改为 $0$。

Takahashi 把棋子从顶点 $1$ 移动到顶点 $2$。

Aoki 把写在顶点 $4$ 上的整数从 $6$ 改为 $0$。

Takahashi 把棋子从顶点 $2$ 移动到顶点 $5$。

Takahashi 选择结束游戏。

游戏结束时,棋子位于顶点 $5$,此时写在顶点 $5$ 上的整数为 $5$,因此 Takahashi 的得分为 $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 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le u_i, v_i \le N$
• 给定的图是一棵树。
• 输入中的所有值均为整数。