问题描述

我们有一个有$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$。

约束条件

• $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

当两个玩家都采取最优策略时，游戏进行如下：

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

在这里，棋子经过的顶点上的数字集合为$\\{2,10,8,6\\}$。这个集合的中位数是$7$，应该打印出来。

示例输入2

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

示例输出2

8

当两个玩家都采取最优策略时，游戏进行如下：

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

在这里，棋子经过的顶点上的数字集合为$\\{6,10\\}$。这个集合的中位数是$8$，应该打印出来。

示例输入3

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

示例输出3

2