Score : $600$ points

问题描述

我们有一棵包含 $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$。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

For example, the median of $\{ 2,2,4 \}$ is $2$, and the median of $\{ 2,4,6,6\}$ is $5$.

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

update @ 2024/3/10 09:39:48