Game on Tree 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$。在游戏结束之前，他们重复以下过程。

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

游戏结束时，Takahashi 的得分就是此时棋子所在顶点上写着的整数。 Takahashi 想使他的得分尽可能大，而 Aoki 想使其尽可能小。 当双方都为各自的目的进行最优操作时，输出 Takahashi 将得到的分数。

输入格式

输入从标准输入以以下格式给出： $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

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$ 给定的图是棵树。 输入中的所有数值都是整数。当双方都最优地进行操作时，下面是游戏的一种可能进行过程。

棋子开始在顶点 $1$。 Aoki 将顶点 $7$ 上的整数从 $10$ 改为 $0$。 Takahashi 将棋子从顶点 $1$ 移动到顶点 $2$。 Aoki 将顶点 $4$ 上的整数从 $6$ 改为 $0$。 Takahashi 将棋子从顶点 $2$ 移动到顶点 $5$。 Takahashi 选择结束游戏。

游戏结束时，棋子位于顶点 $5$，该顶点此时写着的整数为 $5$，因此 Takahashi 的得分将是 $5$。

标签: AtCoder|abc246G

来源

AtCoder|abc246G