树上的游戏 2

题目描述

我们有一棵顶点编号为 $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}$

输出格式

输出在两人都最优地行动时，棋子访问过的顶点上数字所构成的（多重）集合的中位数。

样例

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$，输出 $7$。

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

8

在两人都最优地行动时，游戏过程如下。

太郎将棋子从顶点 $1$ 移动到顶点 $4$。

次郎无法移动棋子，游戏结束。

此时，棋子访问过的顶点上数字构成的集合为 $\{6,10\}$。该集合的中位数为 $8$，输出 $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 \lt v_i \leq N$
• 给定的图是一棵树
• 输入中的值全部为整数