P15943 [JOI Final 2026] JOI 之旅 2 / JOI Tour 2

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$ 恰好被用完。

### 样例 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 分) 无附加限制。