题目描述

$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$

输出格式

答えを出力せよ。

题目大意

给定一个有 $N$ 个顶点的树。顶点编号为 $1,\ \ldots,N$，第 $i$ 条边连接了顶点 $u_i$ 和顶点 $v_i$。另外，每个顶点 $i$ 上都写着一个整数 $h_i$。
有 $K$ 个棋子，第 $i$ 个棋子最初放在顶点 $s_i$ 上。你接下来要重复以下操作：「选择一个棋子，将它从当前所在的顶点移动到与之相邻的任意一个顶点上」。当每个棋子 $i$ 都放在顶点 $t_i$ 上时，操作结束。每个棋子 $i$ 不一定要沿着从顶点 $s_i$ 到顶点 $t_i$ 的最短路径移动。
对于一个状态，我们称所有棋子所在的顶点上写着的整数之和为潜能。如果同一个顶点上有多个棋子，那么这个顶点上的整数要按照棋子的个数累加。
求出操作过程中潜能的最大值的最小可能值是多少。注意，要考虑初始状态和结束状态。

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

4

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

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

101

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

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$
• 与えられるグラフは木

Sample Explanation 1

以下のように操作をすることで操作を通してのポテンシャルの最大値は $4$ となります。 - はじめ、ポテンシャルは $3$。 - 駒 $2$ を頂点 $2$ に移動させる。ポテンシャルは $4$ になる。 - 駒 $2$ を頂点 $1$ に移動させる。ポテンシャルは $2$ になる。 - 駒 $1$ を頂点 $2$ に移動させる。ポテンシャルは $4$ になる。 - 駒 $1$ を頂点 $3$ に移動させる。ポテンシャルは $3$ になる。 ポテンシャルの最大値が $4$ より小さくなるような操作の方法は存在しないため、$4$ が答えです。