配点 : $1000$ 点

問題文

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

出力

答えを出力せよ。

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

4

以下のように操作をすることで操作を通してのポテンシャルの最大値は $4$ となります。

• はじめ、ポテンシャルは $3$。
• 駒 $2$ を頂点 $2$ に移動させる。ポテンシャルは $4$ になる。
• 駒 $2$ を頂点 $1$ に移動させる。ポテンシャルは $2$ になる。
• 駒 $1$ を頂点 $2$ に移動させる。ポテンシャルは $4$ になる。
• 駒 $1$ を頂点 $3$ に移動させる。ポテンシャルは $3$ になる。

ポテンシャルの最大値が $4$ より小さくなるような操作の方法は存在しないため、$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