AT_abc246_g.[ABC246G] Game on Tree 3

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵包含 $N$ 个顶点的有根树，根为顶点 $1$ 。对于 $i = 1, 2, \ldots, N-1$ ，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$ 。此外，除了根以外的每个顶点上都写有一个正整数，具体来说，对于 $i = 2, 3, \ldots, N$ ，顶点 $i$ 上写有正整数 $A_i$ 。

高桥君和青木君将用这棵有根树和一个棋子进行如下对抗游戏：

初始时，棋子放在顶点 $1$ 。之后，重复以下步骤直到游戏结束：

首先，青木君任选一个根以外的顶点，并将该顶点上写的整数改为 $0$ 。
接着，高桥君可以将棋子移动到当前棋子所在顶点的任意一个直接子节点。
然后，如果棋子位于叶子节点，游戏结束。即使不是叶子节点，高桥君也可以选择立即结束游戏。

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

输入格式

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

$N$
$A_2\ A_3\ \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
```

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

说明/提示

限制条件

$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$ 。
青木君将顶点 $7$ 上的整数从 $10$ 改为 $0$ 。
高桥君将棋子从顶点 $1$ 移动到顶点 $2$ 。
青木君将顶点 $4$ 上的整数从 $6$ 改为 $0$ 。
高桥君将棋子从顶点 $2$ 移动到顶点 $5$ 。
高桥君选择结束游戏。

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

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页