问题描述

给定一个有 $N$ 个顶点，编号为 $1, \ldots, N$ 的树。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。此外，顶点 $i$ 上写有整数 $h_i$。
我们有 $K$ 个物品，第 $i$ 个物品最初位于顶点 $s_i$。你将重复以下操作：选择一个物品，并将其移动到与该物品当前所在顶点相邻的顶点之一。当每个物品 $i$ 都在顶点 $t_i$ 时，你将结束此过程。不要求每个物品 $i$ 沿着从顶点 $s_i$ 到顶点 $t_i$ 的最短路径走。
对于物品的排列，其潜力是它所在顶点上写的整数的总和。如果多个物品位于同一个顶点，该顶点上的整数将被加上等于这些物品数量的次数。
找出在过程中（包括初始状态和最终状态）可能的最大潜力的最小值。

约束条件

• $1 \leq N,K \leq 2000$
• $1 \leq u_i,v_i \leq N$
• $1 \leq h_i \leq 10^9$
• $1 \leq s_i,t_i \leq N$
• 给定的图是一棵树。

---

输入

输入以以下格式从标准输入给出：

$N$ $h_1$ $h_2$ $\ldots$ $h_N$ $u_1$ $v_1$ $u_2$ $v_2$ $:$ $u_{N-1}$ $v_{N-1}$ $K$ $s_1$ $t_1$ $s_2$ $t_2$ $:$ $s_K$ $t_K$

输出

打印答案。

---

示例输入 1

3
1 3 2
1 2
2 3
2
1 3
3 1

示例输出 1

4

我们可以使最大潜力在过程中达到 $4$，具体操作如下：

• 初始时，潜力为 $3$。
• 将物品 $2$ 移动到顶点 $2$。此时潜力变为 $4$。
• 将物品 $2$ 移动到顶点 $1$。此时潜力变为 $2$。
• 将物品 $1$ 移动到顶点 $2$。此时潜力变为 $4$。
• 将物品 $1$ 移动到顶点 $3$。此时潜力变为 $3$。

没有办法使过程中的最大潜力小于 $4$，因此答案为 $4$。

---

示例输入 2

7
100 101 1 100 101 1 1000
1 2
2 3
4 5
5 6
1 7
4 7
2
1 3
4 6

示例输出 2

201

---

示例输入 3

5
2 1 100 5 6
1 2
2 3
3 4
3 5
2
2 2
4 5

示例输出 3

101

---

示例输入 4

4
1 2 3 100
1 4
2 4
3 4
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

示例输出 4

115

---

示例输入 5

6
1 100 1 1 10 1000
1 2
2 3
4 5
1 6
4 6
3
1 3
5 5
5 5

示例输出 5

102