分数: 600 点
问题陈述
我们有一棵树 N 顶点编号 1 通过 N。的 i第边缘 (1 \leq i \leq N-1) 连接顶点 u_i 和顶点 v_i和顶点 i (1 \leq i \leq N) 有一个偶数 上面写着 A_i 。太郎和二郎将使用这棵树和一块棋子玩游戏。
最初,该块位于 Vertex 上 1。太郎先走,玩家轮流将棋子移动到与棋子所在顶点直接相连的顶点。然而,该片段不得重新访问它已经访问过的顶点。当棋子无法移动时游戏结束。
Taro 希望在游戏结束前最大化棋子所访问的顶点上所写的(多)组数字的中位数(包括顶点) 1),而 Jiro 希望最小化该值。当两名玩家都发挥最佳状态时,求该组的中位数。
中位数是什么?
一组(多)组的中位数 K 数字定义如下:
- 这 \frac{K+1}{2}- 第一个最小的数字,如果 K 是奇数;
- 的平均值 \frac{K}{2}-th 和 (\frac{K}{2}+1)- 第最小的数字,如果 K 是偶数。
约束
- 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.
- Jiro 从 Vertex 移动棋子 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