当前没有测试数据。

G - 树上的游戏3

得分：600分

问题描述

有一棵有$n$个顶点的根树，顶点1是根。 对于每个$i=1, 2, \ldots, n-1$，第$i$条边连接顶点$u_i$和顶点$v_i$。 除了根以外的每个顶点上都写着一个正整数：对于每个$i=2, 3, \ldots, n$，顶点$i$上写着整数$A_i$。 高桥和青木将使用这棵根树和一枚棋子彼此对战下面的游戏。

棋子在顶点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。

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