题目描述

JOI 国有 $N$ 个城镇，编号为 $1$ 到 $N$。此外，JOI 国有 $N-1$ 条道路，编号为 $1$ 到 $N-1$。道路 $j$ ($1 \leq j \leq N-1$) 双向连接城镇 $U_j$ 和城镇 $V_j$。可以通过若干条道路从任意城镇前往任意其他城镇。

JOI 国的每个城镇都有一家商店。在城镇 $i$ ($1 \leq i \leq N$) 的商店中，一件纪念品的售价为 $A_i$。

今年，JOI 国计划了 $M$ 次旅行。第 $k$ 次旅行 ($1 \leq k \leq M$) 从城镇 $S_k$ 出发，沿着道路前往城镇 $T_k$，且不重复经过同一个城镇。注意，第 $k$ 次旅行同时访问城镇 $S_k$ 和 $T_k$。保证 $S_k \neq T_k$。注意，根据 JOI 国的结构，一次旅行所经过的城镇序列是唯一确定的。

你计划参加其中一次旅行，并在该旅行经过的城镇中恰好选出两个，在每个城镇各买一件纪念品。此外，你希望恰好用完为纪念品准备的全部预算，因此对于 $Q$ 个候选预算中的每一个，你决定调查有多少种实现方式。

给定 JOI 国的道路、纪念品价格、旅行信息以及候选预算 $B_1, B_2, \dots, B_Q$，编写一个程序，计算选择旅行和购买纪念品的城镇的方案数。更确切地说，对于每个 $q$ ($1 \leq q \leq Q$)，计算满足以下所有条件的整数三元组 $(k, u, v)$ 的数量：

• $1 \leq k \leq M$。
• $1 \leq u < v \leq 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 \leq q \leq Q$) 应包含选择旅行和购买纪念品的城镇的方案数，使得预算 $B_q$ 恰好被用完。

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

0
0
4
2
4
1
0

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

1
2
3
3
1

提示

样例 1

首先，每次旅行访问的城镇如下：

• 第 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$ 时，有 $4$ 种方案：$(1, 1, 2)$, $(1, 1, 4)$, $(2, 1, 6)$, $(3, 2, 5)$。
• 预算为 $4$ 时，有 $2$ 种方案：$(1, 1, 3)$, $(1, 2, 4)$。
• 预算为 $5$ 时，有 $4$ 种方案：$(1, 2, 3)$, $(1, 3, 4)$, $(4, 3, 8)$, $(4, 7, 8)$。
• 预算为 $6$ 时，有 $1$ 种方案：$(4, 3, 7)$。

该输入样例满足子任务 $1, 3, 7, 9, 11$ 的限制。

样例 2

该输入样例满足子任务 $1, 2, 3, 6, 7, 8, 9, 10, 11$ 的限制。

限制

• $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$)。
• 可以通过若干条道路从任意城镇前往任意其他城镇。
• $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$。
• 所有输入值均为整数。

子任务

1. (3 分) $N \leq 100, M \leq 100, Q \leq 100$。
2. (4 分) $N \leq 5000, U_j = j, V_j = j + 1$ ($1 \leq j \leq N-1$)。
3. (5 分) $N \leq 5000$。
4. (6 分) $Q = 1, U_j = j, V_j = j + 1$ ($1 \leq j \leq N-1$)。
5. (10 分) $Q = 1$。
6. (7 分) $M \leq 1000, U_j = j, V_j = j + 1$ ($1 \leq j \leq N-1$)。
7. (12 分) $M \leq 1000$。
8. (10 分) $N \leq 50\,000, M \leq 50\,000, U_j = j, V_j = j + 1$ ($1 \leq j \leq N-1$)。
9. (15 分) $N \leq 50\,000, M \leq 50\,000$。
10. (11 分) $U_j = j, V_j = j + 1$ ($1 \leq j \leq N-1$)。
11. (17 分) 无附加限制。