分数: 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。直到游戏结束,他们重复以下过程。
- 首先,Aoki 选择一个非根顶点,并将写在该顶点上的整数替换为 0.
- 接下来,Takahashi 将棋子移动到棋子所在顶点的(直接)子节点。
- 然后,如果棋子在叶子上,游戏结束。即便不是这样,高桥也可以选择立即结束比赛。
游戏结束时,高桥的得分将是当时棋子所在顶点上所写的整数。 高桥希望自己的分数尽可能大,而青木则希望分数尽可能小。 打印当两名玩家都为各自的目的发挥最佳状态时,高桥将得到的分数。
约束
- 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
这是当两个玩家都发挥最佳状态时游戏的可能进展。
- 该作品从 Vertex 开始 1.
- Aoki 更改 Vertex 上写入的整数 7 来自 10 to 0.
- Takahashi 从 Vertex 移动棋子 1 到顶点 2.
- Aoki 更改 Vertex 上写入的整数 4 来自 6 to 0.
- Takahashi 从 Vertex 移动棋子 2 到顶点 5.
- 高桥选择结束游戏。
游戏结束时,棋子位于顶点 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