AT_arc115_f.[ARC115F] Migration

给定一棵有 $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 \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 翻译