题目描述

给定一棵有 $N$ 个顶点的树。顶点编号为 $1,\ldots,N$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。此外，每个顶点 $i$ 上写有一个整数 $h_i$。

有 $K$ 个棋子，第 $i$ 个棋子最初放在顶点 $s_i$ 上。你可以重复进行如下操作：“选择一个棋子，将其移动到当前所在顶点的相邻顶点之一”。当每个棋子 $i$ 都到达顶点 $t_i$ 时，操作结束。每个棋子 $i$ 不要求必须沿最短路径从 $s_i$ 移动到 $t_i$。

对于某一时刻的棋子分布，将所有棋子所在顶点上写的整数加起来，称为该时刻的势能。如果有多个棋子在同一个顶点，则该顶点上的整数要按棋子数量累加。

请你求出，在所有可能的操作方案中，操作过程中势能的最大值的最小可能值是多少。初始状态和结束状态也需要计入。

输入格式

输入按以下格式从标准输入读入。

$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

输出

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

输出

201

样例 3

输入

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

输出

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

输出

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

输出

102

说明/提示

限制条件

• $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$
• 给定的图是一棵树

样例解释 1

通过如下操作，操作过程中的势能最大值为 $4$。

• 初始时，势能为 $3$。
• 将棋子 $2$ 移动到顶点 $2$，势能变为 $4$。
• 将棋子 $2$ 移动到顶点 $1$，势能变为 $2$。
• 将棋子 $1$ 移动到顶点 $2$，势能变为 $4$。
• 将棋子 $1$ 移动到顶点 $3$，势能变为 $3$。

不存在使势能最大值小于 $4$ 的操作方案，因此答案为 $4$。

由 ChatGPT 4.1 翻译