G - 游戏与树2

得分：$600$分

题目描述

我们有一棵有 $N$ 个顶点的树，顶点从 $1$ 到 $N$ 编号。第 $i$ 条边 $(1 \leq i \leq N-1)$ 连接了顶点 $u_i$ 和顶点 $v_i$，并且顶点 $i$ $(1 \leq i \leq N)$ 上画了一个偶数 $A_i$。太郎和次郎将使用这个树和一个棋子来进行游戏。

初始时，棋子位于顶点 $1$ 上。轮到太郎先行，两位玩家轮流将棋子移动到与棋子所在顶点直接相连的顶点上。但是，棋子不能重访它已经访问过的顶点。当棋子无法移动时，游戏结束。

太郎希望使游戏结束前棋子所经过的顶点（包括顶点 $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}$

输出

在两位玩家都采取最优策略的情况下，输出棋子所经过的顶点上数字组成的集合的中位数。

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

7

在两位玩家都采取最优策略的情况下，游戏进行如下。

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

此时，棋子经过的顶点上数字的集合是 $\{2,10,8,6\}$。这个集合的中位数是 $7$，需要输出。

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

8

在两位玩家都采取最优策略的情况下，游戏进行如下。

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

此时，棋子经过的顶点上数字的集合是 $\{6,10\}$。这个集合的中位数是 $8$，需要输出。

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

2