E - JOI ツアー 2 (JOI Tour 2) Editorial /

Time Limit: 7 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

There are N towns in the country of JOI, numbered from 1 to N. Also, there are N-1 roads in the country of JOI, numbered from 1 to N-1. Road j (1 \leq j \leq N-1) connects town U_j and town V_j in both directions. It is possible to travel from any town to any other town by using some number of roads.

There is one shop in each town in the country of JOI. In the shop in town i (1 \leq i \leq N), a souvenir is sold for price A_i.

This year, M tours are planned in the country of JOI. The k-th tour (1 \leq k \leq M) starts from town S_k and travels by roads to town T_k without visiting the same town twice. Note that the k-th tour visits both towns S_k and T_k. It is guaranteed that S_k \neq T_k. Note that, from the structure of the country of JOI, the sequence of towns visited by a tour is uniquely determined.

You are planning to participate in one of these tours and buy one souvenir in each of exactly two of the towns visited on the tour. Moreover, you want to use up exactly the entire budget prepared for souvenirs, so for each of Q candidate budgets, you decided to investigate in how many ways this can be done.

Given the roads in the country of JOI, the prices of the souvenirs, the information on the tours, and the candidate budgets B_1, B_2, \ldots, B_Q, write a program that computes the number of ways to choose a tour and the towns in which to buy souvenirs. More formally, for each q (1 \leq q \leq Q), write a program that computes the number of triples of integers (k,u,v) satisfying all of the following conditions.

  • 1\leq k\leq M.
  • 1\leq u < v \leq N.
  • The k-th tour visits towns u and v.
  • A_u+A_v=B_q.

Input

Read the following data from the standard input.

N
A_1 A_2 \cdots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
M
S_1 T_1
S_2 T_2
\vdots
S_M T_M
Q
B_1 B_2 \cdots B_Q

Output

Write Q lines to the standard output. The q-th line (1\leq q\leq Q) should contain the number of ways to choose a tour and the towns in which to buy souvenirs so that the budget B_q is used up exactly.

Constraints

  • 2 \leq N \leq 100\,000.
  • 1\leq A_i\leq N (1 \leq i \leq N).
  • 1\leq U_j\leq N (1 \leq j \leq N-1).
  • 1\leq V_j\leq N (1 \leq j \leq N-1).
  • It is possible to travel from any town to any other town by using some number of roads.
  • 1\leq M \leq 200\,000.
  • 1\leq S_k\leq N (1\leq k\leq M).
  • 1\leq T_k\leq N (1\leq k\leq M).
  • S_k\neq T_k (1\leq k\leq M).
  • 1\leq Q\leq 2\,000.
  • 1\leq B_1 < B_2 < \cdots < B_Q\leq 2N.
  • All input values are integers.

Subtasks

  1. (3 points) N\leq 100, M\leq 100, Q\leq 100.
  2. (4 points) N\leq 5\,000, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
  3. (5 points) N\leq 5\,000.
  4. (6 points) Q= 1, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
  5. (10 points) Q= 1.
  6. (7 points) M\leq 1000, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
  7. (12 points) M\leq 1000.
  8. (10 points) N\leq 50\,000, M\leq 50\,000, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
  9. (15 points) N\leq 50\,000, M\leq 50\,000.
  10. (11 points) U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
  11. (17 points) No additional constraints.

Sample Input 1

8
1 2 3 2 1 2 3 2
2 3
7 8
4 3
1 2
7 3
2 5
6 1
4
1 4
1 6
2 5
3 8
7
1 2 3 4 5 6 16

Sample Output 1

0
0
4
2
4
1
0

First, the towns visited by each tour are as follows.

  • The 1st tour visits towns 1, 2, 3, 4.
  • The 2nd tour visits towns 1, 6.
  • The 3rd tour visits towns 2, 5.
  • The 4th tour visits towns 3, 7, 8.

Represent a method of participating in the k-th tour and buying souvenirs in towns u and v by (k,u,v). Then, for each candidate budget, the ways to use up the budget exactly are as follows.

  • There are 0 ways to use up budget 1.
  • There are 0 ways to use up budget 2.
  • There are 4 ways to use up budget 3: (1,1,2), (1,1,4), (2,1,6), (3,2,5).
  • There are 2 ways to use up budget 4: (1,1,3), (1,2,4).
  • There are 4 ways to use up budget 5: (1,2,3), (1,3,4), (4,3,8), (4,7,8).
  • There is 1 way to use up budget 6: (4,3,7).
  • There are 0 ways to use up budget 16.

This input example satisfies the constraints of subtasks 1, 3, 7, 9, 11.

Sample Input 2

8
8 2 3 6 1 4 1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1
1 8
5
2 4 5 10 15

Sample Output 2

1
2
3
3
1

This input example satisfies the constraints of subtasks 1, 2, 3, 6, 7, 8, 9, 10, 11.

配点： 100 点

問題文

JOI 国には N 個の街があり，1 から N までの番号が付けられている．また，JOI 国には N-1 本の道路があり，1 から N-1 までの番号が付けられている． 道路 j (1\leqq j\leqq N-1) は街 U_j と街 V_j を双方向に結んでいる．どの街からどの街へも何本かの道路を通ることによって移動することができる．

JOI 国のそれぞれの街には店が 1 つあり，街 i (1\leqq i\leqq N) の店ではお土産を値段 A_i で売っている．

JOI 国では今年，M 個のツアーが計画されている． k 番目 (1\leqq k\leqq M) のツアーは，街 S_k を出発し，街 T_k まで同じ街を 2 回訪れることなく道路を通って移動するものである．ただし k 番目のツアーは街 S_k, T_k も訪れる．また，S_k\neq T_k であることが保証される． JOI 国の構造から，ツアーがどの街を訪れるかが 1 通りに定まることに注意せよ．

あなたは，これらのツアーのうちひとつに参加して，訪れる街のうちちょうど 2 つの街でお土産を 1 つずつ購入することを計画している． さらに，お土産のために用意した予算をちょうど使い切るようにしたいと考えているため，Q 通りの予算の候補についてそのような方法が何通りあるのかを調べることにした．

JOI 国の道路とお土産の値段，ツアーの情報，および予算の候補 B_1, B_2, \ldots, B_Q が与えられたとき， ツアーおよびお土産を購入する街を選ぶ方法が何通りあるかを求めるプログラムを作成せよ． より形式的には各 q (1\leqq q\leqq Q) について，整数の組 (k,u,v) であって以下の条件をすべて満たすものの個数を求めるプログラムを作成せよ．

  • 1\leqq k\leqq M．
  • 1\leqq u < v \leqq N．
  • k 番目のツアーは街 u, v を訪れる．
  • A_u+A_v=B_q．

入力

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

N
A_1 A_2 \cdots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
M
S_1 T_1
S_2 T_2
\vdots
S_M T_M
Q
B_1 B_2 \cdots B_Q

出力

標準出力に Q 行出力せよ．q 行目 (1\leqq q\leqq Q) には，予算 B_q をちょうど使い切るようにツアーおよびお土産を購入する街を選ぶ方法が何通りあるかを出力せよ．

制約

  • 2 \leqq N \leqq 100\,000．
  • 1\leqq A_i\leqq N (1 \leqq i \leqq N)．
  • 1\leqq U_j\leqq N (1 \leqq j \leqq N-1)．
  • 1\leqq V_j\leqq N (1 \leqq j \leqq N-1)．
  • どの 2 つの街の間も，いくつかの道路を経由して移動することができる．
  • 1\leqq M \leqq 200\,000．
  • 1\leqq S_k\leqq N (1\leqq k\leqq M)．
  • 1\leqq T_k\leqq N (1\leqq k\leqq M)．
  • S_k\neq T_k (1\leqq k\leqq M)．
  • 1\leqq Q\leqq 2\,000．
  • 1\leqq B_1 < B_2 < \cdots < B_Q\leqq 2N．
  • 入力される値はすべて整数である．

小課題

  1. (3 点) N\leqq 100，M\leqq 100，Q\leqq 100．
  2. (4 点) N\leqq 5\,000，U_j=j (1\leqq j\leqq N-1)，V_j=j+1 (1\leqq j\leqq N-1)．
  3. (5 点) N\leqq 5\,000．
  4. (6 点) Q= 1，U_j=j (1\leqq j\leqq N-1)，V_j=j+1 (1\leqq j\leqq N-1)．
  5. (10 点) Q= 1．
  6. (7 点) M\leqq 1000，U_j=j (1\leqq j\leqq N-1)，V_j=j+1 (1\leqq j\leqq N-1)．
  7. (12 点) M\leqq 1000．
  8. (10 点) N\leqq 50\,000, M\leqq 50\,000，U_j=j (1\leqq j\leqq N-1)，V_j=j+1 (1\leqq j\leqq N-1)．
  9. (15 点) N\leqq 50\,000, M\leqq 50\,000．
  10. (11 点) U_j=j (1\leqq j\leqq N-1)，V_j=j+1 (1\leqq j\leqq N-1)．
  11. (17 点) 追加の制約はない．

入力例 1

8
1 2 3 2 1 2 3 2
2 3
7 8
4 3
1 2
7 3
2 5
6 1
4
1 4
1 6
2 5
3 8
7
1 2 3 4 5 6 16

出力例 1

0
0
4
2
4
1
0

まずそれぞれのツアーが訪れる街は次の通りである．

  • 1 番目のツアーは街 1, 2, 3, 4 を訪れる．
  • 2 番目のツアーは街 1, 6 を訪れる．
  • 3 番目のツアーは街 2, 5 を訪れる．
  • 4 番目のツアーは街 3, 7, 8 を訪れる．

k 番目のツアーに参加して街 u, v でお土産を購入するという方法を (k,u,v) と表すとき，それぞれの予算の候補について，予算を使い切る方法は次の通りである．

  • 予算 1 を使い切る方法は 0 通りである．
  • 予算 2 を使い切る方法は 0 通りである．
  • 予算 3 を使い切る方法は (1,1,2), (1,1,4), (2,1,6), (3,2,5) の 4 通りである．
  • 予算 4 を使い切る方法は (1,1,3), (1,2,4) の 2 通りである．
  • 予算 5 を使い切る方法は (1,2,3),(1,3,4),(4,3,8),(4,7,8) の 4 通りである．
  • 予算 6 を使い切る方法は (4,3,7) の 1 通りである．
  • 予算 16 を使い切る方法は 0 通りである．

この入力例は小課題 1, 3, 7, 9, 11 の制約を満たす．

入力例 2

8
8 2 3 6 1 4 1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1
1 8
5
2 4 5 10 15

出力例 2

1
2
3
3
1

この入力例は小課題 1, 2, 3, 6, 7, 8, 9, 10, 11 の制約を満たす．