← 返回题目列表

Codeforces · 533/A

A. 伯兰德矿工

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

Berland 最大的金矿由 n 个洞穴组成,通过 n - 1 个过渡连接。矿井的入口通向 1 号洞穴,可以通过沿着过渡区移动从该洞穴到达矿井的任何剩余洞穴。

该矿场由 InMine Inc. 开发,有 k 名矿工为其工作。公司每天都会将矿工分类到洞穴中,以便每个洞穴最多有一名矿工在那里工作。

对于每个洞穴,我们知道其天花板的高度 hi(以米为单位),对于每个矿工,我们知道他的高度 sj(也以米为单位)。如果一个矿工的身高不超过他所在的洞穴天花板的高度,那么他就可以舒服地站在那里,否则他就必须弯腰,这让他不高兴。

不幸的是,Berland 的矿工通常会罢工,因此 InMine 尽一切努力让矿工对他们的工作条件感到满意。为了确保没有矿工罢工,你需要确保没有矿工在从矿井入口到洞穴的途中任何时候都不必弯腰(特别是他必须能够在他工作的洞穴中舒适地站立)。

为了达到这个目标,你可以选择一个洞穴并将其天花板高度增加几米。然而,扩大洞穴是一个昂贵且复杂的过程。这就是为什么 InMine Inc. 要求您要么确定应将某个洞穴的天花板抬高的最小米数,以便能够将矿工分类到洞穴中并使所有矿工对他们的工作条件感到满意,要么确定仅提高一个洞穴的天花板是不可能实现的。

输入

第一行包含整数 n (1 ≤ n ≤ 5·105) — 矿井中的洞穴数量。

然后是由 n 个正整数 h1, h2, ..., hn (1 ≤ hi ≤ 109) 组成的线,其中 hi 是第 i 个洞穴中天花板的高度。

接下来的 n - 1 行包含洞穴之间过渡的描述。每条线的形式为 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi),其中 ai 和 bi 是由路径连接的洞穴的数量。

下一行包含整数 k (1 ≤ k ≤ n)。

最后一行包含 k 个整数 s1, s2, ..., sk (1 ≤ sj ≤ 109),其中 sj 是第 j 个矿工的身高。

输出

在单行中打印出您需要在某个洞穴中提高天花板的最小米数,以便所有矿工都可以被分类到洞穴中并对工作条件感到满意。如果不可能,则打印 - 1。如果最初是可能的并且不需要提高任何上限,则打印 0。

示例

输入 #1

6
5 8 4 6 3 12
1 2
1 3
4 2
2 5
6 3
6
7 4 2 5 3 11

输出 #1

6

输入 #2

7
10 14 7 12 4 50 1
1 2
2 3
2 4
5 1
6 5
1 7
6
7 3 4 8 8 10

输出 #2

0

输入 #3

3
4 2 8
1 2
1 3
2
17 15

输出 #3

-1

注意

在第一个样本测试中,我们应该将第一个洞穴的天花板高度从 5 增加到 11。之后,我们可以按如下方式分配矿工(首先是矿工的索引,然后是洞穴的索引):$$1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 5, 4 \rightarrow 4, 5 \rightarrow 6, 6 \rightarrow 1$$。

在第二个样本测试中,无需执行任何操作,因为已经可以按如下方式分配矿工:$$1 \rightarrow 3, 2 \rightarrow 5, 3 \rightarrow 6, 4 \rightarrow 1, 5 \rightarrow 2, 6 \rightarrow 4$$。

在第三个样本测试中这是不可能的。