AT_abc218_g [ABC218G] Game on Tree 2

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

输入以如下格式从标准输入读入： > $N$ > $A_1\ A_2\ \ldots\ A_N$ > $u_1\ v_1$ > $u_2\ v_2$ > $\vdots$ > $u_{N-1}\ v_{N-1}$

请输出当两人都采取最优策略时，棋子访问过的顶点上数字集合的中位数。

### 限制条件 - $2 \leq N \leq 10^5$ - $2 \leq A_i \leq 10^9$ - $A_i$ 为偶数 - $1 \leq u_i < v_i \leq N$ - 给定的图是一棵树 - 输入均为整数 ### 样例解释 1 当两人都采取最优策略时，游戏过程如下： - 太郎君将棋子从顶点 $1$ 移动到顶点 $5$ - 次郎君将棋子从顶点 $5$ 移动到顶点 $4$ - 太郎君将棋子从顶点 $4$ 移动到顶点 $3$ - 次郎君无法再移动棋子，游戏结束 棋子访问过的顶点上的数字集合为 $\{2,10,8,6\}$，其中位数为 $7$，因此输出 $7$。 ### 样例解释 2 当两人都采取最优策略时，游戏过程如下： - 太郎君将棋子从顶点 $1$ 移动到顶点 $4$ - 次郎君无法再移动棋子，游戏结束 棋子访问过的顶点上的数字集合为 $\{6,10\}$，其中位数为 $8$，因此输出 $8$。 由 ChatGPT 4.1 翻译