#arc115f. [arc115_f]Migration

[arc115_f]Migration

問題文

NN 頂点の木が与えられます。頂点には 1,ldots,N1, \\ldots,N の番号がついており、ii 番目の辺は頂点 uiu_i と頂点 viv_i をつないでいます。また、頂点 ii には整数 hih_i が書かれています。
駒が KK 個あり、ii 番目の駒ははじめ頂点 sis_i に置かれています。あなたはこれから「一つ駒を選び、それが現在置かれている頂点に隣接するいずれかの頂点に移動させる」という操作を繰り返します。 各駒 ii が頂点 tit_i に置かれている状態になったら操作を終了します。各駒 ii を頂点 sis_i から頂点 tit_i へ最短経路で移動させる必要はありません
ある駒の配置に対して、それぞれの駒が置かれている頂点に書かれた整数を足し合わせた値をポテンシャルと呼ぶことにします。ただし、同じ頂点に複数の駒がある場合、その頂点の整数はその駒の個数だけ足し合わせるものとします。
操作を通してのポテンシャルの最大値は最小でいくつになるか求めてください。ただし、はじめの状態と終わりの状態も考えるものとします。

制約

  • 1leqN,Kleq20001 \\leq N,K \\leq 2000
  • 1lequi,vileqN1 \\leq u_i,v_i \\leq N
  • 1leqhileq1091 \\leq h_i \\leq 10^9
  • 1leqsi,tileqN1 \\leq s_i,t_i \\leq N
  • 与えられるグラフは木

入力

入力は以下の形式で標準入力から与えられる。

NN h1h_1 h2h_2 ldots\\ldots hNh_N u1u_1 v1v_1 u2u_2 v2v_2 :: uN1u_{N-1} vN1v_{N-1} KK s1s_1 t1t_1 s2s_2 t2t_2 :: sKs_K tKt_K

出力

答えを出力せよ。


入力例 1

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

出力例 1

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

  • はじめ、ポテンシャルは 33
  • 22 を頂点 22 に移動させる。ポテンシャルは 44 になる。
  • 22 を頂点 11 に移動させる。ポテンシャルは 22 になる。
  • 11 を頂点 22 に移動させる。ポテンシャルは 44 になる。
  • 11 を頂点 33 に移動させる。ポテンシャルは 33 になる。

ポテンシャルの最大値が 44 より小さくなるような操作の方法は存在しないため、44 が答えです。


入力例 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