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$）被棋子访问的顶点上所写数字的（多重）集合的中位数，而次郎想要最小化该值。求在双方都最优操作时该集合的中位数。

输入格式

输入以如下格式从标准输入给出： $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$

输出格式

当双方都最优操作时，输出棋子访问的顶点上所写数字的（多重）集合的中位数。

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

7

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

8

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

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$ 移动到顶点 $5$。 次郎将棋子从顶点 $5$ 移动到顶点 $4$。 太郎将棋子从顶点 $4$ 移动到顶点 $3$。 次郎无法移动棋子，游戏结束。

此时，棋子访问的顶点上写的数字的集合是 $\{2,10,8,6\}$。该集合的中位数是 $7$，应当输出该值。
当双方都最优操作时，游戏过程如下。

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

此时，棋子访问的顶点上写的数字的集合是 $\{6,10\}$。该集合的中位数是 $8$，应当输出该值。

标签: AtCoder|abc218G

来源

AtCoder|abc218G