← 返回题目列表

Codeforces · 796/C

C. 银行黑客攻击

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

虽然因赞恩成功找到了他心爱的骨头,但他的主人赞恩却还没有回来。为了寻找赞恩,他需要很多钱,但遗憾的是他没有。为了解决这个问题,他决定入侵银行。

有 n 个组,编号从 1 到 n。还有 n - 1 根电线连接各组。所有银行最初都是在线的。每个银行也有其初始强度:银行 i 的初始强度为 ai。

在继续之前,让我们定义一些关键字。当且仅当存在直接连接银行 i 和银行 j 的电线时,银行 i 和银行 j 是相邻的。银行i和银行j是半相邻的当且仅当存在网上银行k使得银行i和银行k相邻并且银行k和银行j相邻。

当一家银行被黑客攻击时,它会离线(并且不再在线),并且与其相邻或半相邻的其他银行的强度增加 1。

为了开始他的计划,Inzane 将首先选择一家银行进行黑客攻击。确实,这样的银行的实力绝对不能超过他电脑的实力。此后,他将反复选择接下来要攻击的银行,直到所有银行都被攻击为止,但当且仅当满足所有这些条件时,他才能继续攻击银行x:

1. 银行 x 上线。也就是说,银行 x 还没有被黑客入侵。
2. 银行 x 与某离线银行相邻。
3. 银行 x 的强度小于或等于 Inzane 计算机的强度。

确定 Inzane 破解所有银行所需的最低计算机强度。

输入

第一行包含一个整数 n (1 ≤ n ≤ 3·105) — 存储体总数。

第二行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) – 银行的实力。

接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 意味着有一条电线直接连接组 ui 和 vi。

保证电线以这样的方式连接银行,Inzane 可以使用具有适当强度的计算机以某种方式破解所有银行。

输出

打印一个整数——Inzane 完成目标所需的最低计算机强度。

示例

输入 #1

5
1 2 3 4 5
1 2
2 3
3 4
4 5

输出 #1

5

输入 #2

7
38 -29 87 93 39 28 -55
1 2
2 5
3 2
2 4
1 7
7 6

输出 #2

93

输入 #3

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

输出 #3

8

注意

在第一个示例中,Inzane 可以使用强度为 5 的计算机入侵所有银行。具体方法如下:

- 最初,银行的优势为 [1, 2, 3, 4, 5]。
- 他黑掉了银行5,然后银行的优势变成了[1, 2, 4, 5,  - ]。
- 他黑掉了银行4,然后银行的优势变成了[1, 3, 5,  - ,  - ]。
- 他黑掉了银行3,然后银行的优势变成了[2, 4,  - ,  - ,  - ]。
- 他黑掉了银行2,然后银行的优势变成了[3,  - ,  - ,  - ,  - ]。
- 他通过侵入 1 号银行来完成他的目标。

在第二个示例中,Inzane 可以按顺序攻击银行 4、2、3、1、5、7 和 6。这样,他就可以使用强度为 93 的计算机入侵所有银行。