F - Migration Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 1

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

出力例 1

4

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

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

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

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

Score : 1000 points

Problem Statement

Given is a tree with N vertices numbered 1, \ldots, N. The i-th edge connects Vertex u_i and Vertex v_i. Additionally, Vertex i has an integer h_i written on it.
We have K pieces, the i-th of which is initially on Vertex s_i. You will repeat the following operation: choose a piece and move it to one of the vertices adjacent to the vertex the piece is currently on. You will end this process when each piece i is on Vertex t_i. It is not required for each piece i to go along the shortest path from Vertex s_i to Vertex t_i.
For an arrangement of the pieces, let its potential be the sum of the integers written on the vertices the pieces are on. If multiple pieces are on the same vertex, the integer on that vertex is added the number of times equal to that number of pieces.
Find the minimum possible value of the maximum potential during the process, including the initial and final states.

Constraints

  • 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
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

4

We can make 4 the maximum potential during the process, as follows:

  • Initially, the potential is 3.
  • Move Piece 2 to Vertex 2. The potential is now 4.
  • Move Piece 2 to Vertex 1. The potential is now 2.
  • Move Piece 1 to Vertex 2. The potential is now 4.
  • Move Piece 1 to Vertex 3. The potential is now 3.

There is no way to make the maximum potential during the process less than 4, so the answer is 4.

Sample Input 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

Sample Output 2

201

Sample Input 3

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

Sample Output 3

101

Sample Input 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

Sample Output 4

115

Sample Input 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

Sample Output 5

102