← 返回题目列表

AtCoder · abc246_g

G. 树上的游戏 3

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一棵有根的树 N 顶点,顶点 1 是根。 对于每个 i = 1, 2, \ldots, N-1, i第一条边连接顶点 u_i 和顶点 v_i。 除根之外的每个顶点都写有一个正整数:对于每个 i = 2, 3, \ldots, N,写入 Vertex 的整数 i is A_i。 高桥和青木将使用这棵有根的树和一块棋子来相互进行以下游戏。

该作品从 Vertex 开始 1。直到游戏结束,他们重复以下过程。

  1. 首先,Aoki 选择一个非根顶点,并将写在该顶点上的整数替换为 0.
  2. 接下来,Takahashi 将棋子移动到棋子所在顶点的(直接)子节点。
  3. 然后,如果棋子在叶子上,游戏结束。即便不是这样,高桥也可以选择立即结束比赛。

游戏结束时,高桥的得分将是当时棋子所在顶点上所写的整数。 高桥希望自己的分数尽可能大,而青木则希望分数尽可能小。 打印当两名玩家都为各自的目的发挥最佳状态时,高桥将得到的分数。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq u_i, v_i \leq N
  • 给定的图是一棵树。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_2 \ldots A_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

输出

打印答案。


示例输入 1

7
2 4 6 5 6 10
1 2
1 3
2 4
2 5
5 6
5 7

示例输出 1

5

这是当两个玩家都发挥最佳状态时游戏的可能进展。

  1. 该作品从 Vertex 开始 1.
  2. Aoki 更改 Vertex 上写入的整数 7 来自 10 to 0.
  3. Takahashi 从 Vertex 移动棋子 1 到顶点 2.
  4. Aoki 更改 Vertex 上写入的整数 4 来自 6 to 0.
  5. Takahashi 从 Vertex 移动棋子 2 到顶点 5.
  6. 高桥选择结束游戏。

游戏结束时,棋子位于顶点 5,其中整数 当时写的是 5 ,所以高桥的分数将是 5.


示例输入 2

30
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 32 38 84 49 93 53 26 13 25
13 15
14 22
17 24
12 3
4 3
5 8
26 15
3 2
2 9
4 25
4 13
2 10
28 15
6 4
2 5
19 9
2 7
2 14
23 30
17 2
7 16
21 13
13 23
13 20
1 2
6 18
27 6
21 29
11 8

示例输出 2

70