AT_abc218_g [ABC218G] Game on Tree 2

题目描述

有一棵包含 $N$ 个顶点的树，每个顶点编号为 $1$ 到 $N$。第 $i$ 条边（$1 \leq i \leq N-1$）连接顶点 $u_i$ 和顶点 $v_i$。每个顶点 $i$（$1 \leq i \leq N$）上写有一个偶数 $A_i$。

太郎君和次郎君用这棵树和一个棋子进行游戏。

一开始，棋子放在顶点 $1$。两人轮流行动，太郎君先手。每次行动时，可以将棋子从当前顶点移动到与之直接相连的另一个顶点，但不能移动到已经访问过的顶点。当无法再移动棋子时，游戏结束。

太郎君希望最大化游戏结束时棋子访问过的所有顶点（包括顶点 $1$）上数字的（多重）集合的中位数，次郎君则希望最小化该中位数。请你求出当两人都采取最优策略时，棋子访问过的顶点上数字集合的中位数。

中位数的定义如下：设集合大小为 $K$，

• 当 $K$ 为奇数时，中位数为从小到大第 $\frac{K+1}{2}$ 个数；
• 当 $K$ 为偶数时，中位数为从小到大第 $\frac{K}{2}$ 个数与第 $\frac{K}{2}+1$ 个数的平均值。

例如，$\{2,2,4\}$ 的中位数为 $2$，$\{2,4,6,6\}$ 的中位数为 $5$。

输入格式

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

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

输出格式

请输出当两人都采取最优策略时，棋子访问过的顶点上数字集合的中位数。

输入输出样例 #1

输入 #1

5
2 4 6 8 10
4 5
3 4
1 5
2 4

输出 #1

7

输入输出样例 #2

输入 #2

5
6 4 6 10 8
1 4
1 2
1 5
1 3

输出 #2

8

输入输出样例 #3

输入 #3

6
2 2 6 4 6 6
1 2
2 3
4 6
2 5
2 6

输出 #3

2

说明/提示

限制条件

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

样例解释 1

当两人都采取最优策略时，游戏过程如下：

• 太郎君将棋子从顶点 $1$ 移动到顶点 $5$
• 次郎君将棋子从顶点 $5$ 移动到顶点 $4$
• 太郎君将棋子从顶点 $4$ 移动到顶点 $3$
• 次郎君无法再移动棋子，游戏结束

棋子访问过的顶点上的数字集合为 $\{2,10,8,6\}$，其中位数为 $7$，因此输出 $7$。

样例解释 2

当两人都采取最优策略时，游戏过程如下：

• 太郎君将棋子从顶点 $1$ 移动到顶点 $4$
• 次郎君无法再移动棋子，游戏结束

棋子访问过的顶点上的数字集合为 $\{6,10\}$，其中位数为 $8$，因此输出 $8$。

由 ChatGPT 4.1 翻译