AT_abc246_g [ABC246G] Game on Tree 3

题目描述

有一棵包含 $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. 然后，如果棋子位于叶子节点，游戏结束。即使不是叶子节点，高桥君也可以选择立即结束游戏。

游戏结束时，棋子所在顶点上当前写的整数即为高桥君的得分。高桥君希望最大化自己的得分，青木君则希望最小化高桥君的得分。请输出在双方都采取最优策略时高桥君的得分。

输入格式

输入以如下格式从标准输入读入：

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

输出格式

输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

5

输入输出样例 #2

输入 #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

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq u_i, v_i \leq N$
• 给定的图是一棵树。
• 所有输入均为整数。

样例解释 1

当双方都采取最优策略时，游戏可能的进行过程如下：

1. 初始时，棋子在顶点 $1$。
2. 青木君将顶点 $7$ 上的整数从 $10$ 改为 $0$。
3. 高桥君将棋子从顶点 $1$ 移动到顶点 $2$。
4. 青木君将顶点 $4$ 上的整数从 $6$ 改为 $0$。
5. 高桥君将棋子从顶点 $2$ 移动到顶点 $5$。
6. 高桥君选择结束游戏。

此时，棋子在顶点 $5$，顶点 $5$ 上的整数为 $5$，所以高桥君的得分为 $5$。

由 ChatGPT 4.1 翻译