102186: [AtCoder]ABC218 G - Game on Tree 2
Description
Score : $600$ points
Problem Statement
We have a tree with $N$ vertices numbered $1$ through $N$. The $i$-th edge $(1 \leq i \leq N-1)$ connects Vertex $u_i$ and Vertex $v_i$, and Vertex $i$ $(1 \leq i \leq N)$ has an even number $A_i$ written on it. Taro and Jiro will play a game using this tree and a piece.
Initially, the piece is on Vertex $1$. With Taro going first, the players alternately move the piece to a vertex directly connected to the vertex on which the piece lies. However, the piece must not revisit a vertex it has already visited. The game ends when the piece gets unable to move.
Taro wants to maximize the median of the (multi-)set of numbers written on the vertices visited by the piece before the end of the game (including Vertex $1$), and Jiro wants to minimize this value. Find the median of this set when both players play optimally.
What is median?
The median of a (multi-)set of $K$ numbers is defined as follows:
- the $\frac{K+1}{2}$-th smallest number, if $K$ is odd;
- the average of the $\frac{K}{2}$-th and $(\frac{K}{2}+1)$-th smallest numbers, if $K$ is even.
Constraints
- $2 \leq N \leq 10^5$
- $2 \leq A_i \leq 10^9$
- $A_i$ is even.
- $1 \leq u_i < v_i \leq N$
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
Output
Print the median of the (multi-)set of numbers written on the vertices visited by the piece when both players play optimally.
Sample Input 1
5 2 4 6 8 10 4 5 3 4 1 5 2 4
Sample Output 1
7
When both players play optimally, the game goes as follows.
- Taro moves the piece from Vertex $1$ to Piece $5$.
- Jiro moves the piece from Vertex $5$ to Piece $4$.
- Taro moves the piece from Vertex $4$ to Piece $3$.
- Jiro cannot move the piece, so the game ends.
Here, the set of numbers written on the vertices visited by the piece is $\{2,10,8,6\}$. The median of this set is $7$, which should be printed.
Sample Input 2
5 6 4 6 10 8 1 4 1 2 1 5 1 3
Sample Output 2
8
When both players play optimally, the game goes as follows.
- Taro moves the piece from Vertex $1$ to Piece $4$.
- Jiro cannot move the piece, so the game ends.
Here, the set of numbers written on the vertices visited by the piece is $\{6,10\}$. The median of this set is $8$, which should be printed.
Sample Input 3
6 2 2 6 4 6 6 1 2 2 3 4 6 2 5 2 6
Sample Output 3
2
Input
题意翻译
给定一棵树，以及树各节点的点权（点权为偶数）。起初有一个棋子在树的根结点（结点 $1$）处。 - $A$ 与 $B$ 两人轮流操作：将棋子移动到其所在节点的某个叶子节点。 - 到某个节点的得分定义为：棋子经过所有结点点权的中位数。$K$ 个数的中位数定义如下： - 当 $K$ 为奇数时，中位数为 $K$ 个数中第 $\frac{K+1}{2}$ 小的值。 - 当 $K$ 为偶数时，中位数为 $K$ 个数中第 $\frac{K}{2}$ 小与第 $\frac{K}{2}+1$ 小的两数的平均值。 - $A$ 希望最后得分尽可能大，$B$ 希望最后得分尽可能小。 - 当棋子到达某个叶节点时，游戏结束。 若 $A$ 先手操作，$A$，$B$ 都采取最优策略，求最终得分。Output
分数：600分
问题描述
我们有一个包含$N$个顶点的树，顶点从1到$N$编号。第$i$条边（$1 \leq i \leq N-1$）连接顶点$u_i$和顶点$v_i$，每个顶点$ i $ $(1 \leq i \leq N)$上都写有一个偶数$A_i$。Taro和Jiro将使用这个游戏树和一个棋子进行游戏。
最初，棋子在顶点1上。Taro先走，玩家交替将棋子移动到棋子所在顶点直接相连的顶点。但是，棋子不能访问已经访问过的顶点。当棋子无法移动时，游戏结束。
Taro想要最大化棋子在游戏结束前（包括顶点1）访问的顶点上写的数字（多重）集合的中位数，而Jiro想要最小化这个值。当两个玩家都发挥最优时，找出这个集合的中位数。
什么是中位数？
一个（多重）集合的中位数定义如下：
- 如果$K$是奇数，则为第$\frac{K+1}{2}$小的数字；
- 如果$K$是偶数，则为第$\frac{K}{2}$小和第$(\frac{K}{2}+1)$小的数字的平均值。
约束条件
- $2 \leq N \leq 10^5$
- $2 \leq A_i \leq 10^9$
- $A_i$是偶数。
- $1 \leq u_i < v_i \leq N$
- 给定的图是一棵树。
- 输入中的所有值都是整数。
输入
从标准输入按以下格式给出输入：
$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
输出
当两个玩家都发挥最优时，打印棋子访问的顶点上写的数字（多重）集合的中位数。
样例输入1
5 2 4 6 8 10 4 5 3 4 1 5 2 4
样例输出1
7
当两个玩家都发挥最优时，游戏如下进行。
- Taro将棋子从顶点1移动到顶点5。
- Jiro将棋子从顶点5移动到顶点4。
- Taro将棋子从顶点4移动到顶点3。
- Jiro无法移动棋子，所以游戏结束。
这里，棋子访问的顶点上写的数字集合为$\{2,10,8,6\}$。这个集合的中位数为7，应打印出来。
样例输入2
5 6 4 6 10 8 1 4 1 2 1 5 1 3
样例输出2
8
当两个玩家都发挥最优时，游戏如下进行。
- Taro将棋子从顶点1移动到顶点4。
- Jiro无法移动棋子，所以游戏结束。
这里，棋子访问的顶点上写的数字集合为$\{6,10\}$。这个集合的中位数为8，应打印出来。
样例输入3
6 2 2 6 4 6 6 1 2 2 3 4 6 2 5 2 6
样例输出3
2