← 返回题目列表

AtCoder · abc218_g

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 。太郎和二郎将使用这棵树和一块棋子玩游戏。

最初,该块位于 Vertex 上 1。太郎先走,玩家轮流将棋子移动到与棋子所在顶点直接相连的顶点。然而,该片段不得重新访问它已经访问过的顶点。当棋子无法移动时游戏结束。

Taro 希望在游戏结束前最大化棋子所访问的顶点上所写的(多)组数字的中位数(包括顶点) 1),而 Jiro 希望最小化该值。当两名玩家都发挥最佳状态时,求该组的中位数。

中位数是什么?

一组(多)组的中位数 K 数字定义如下:

  • 这 \frac{K+1}{2}- 第一个最小的数字,如果 K 是奇数;
  • 的平均值 \frac{K}{2}-th 和 (\frac{K}{2}+1)- 第最小的数字,如果 K 是偶数。
例如,中位数 \{ 2,2,4 \} is 2,以及中位数 \{ 2,4,6,6\} is 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.
  • 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