AT_joi2026final_e JOI ツアー 2 (JOI Tour 2)

在 JOI 国有 $N$ 个城镇，编号为 $1$ 到 $N$。此外，该国有 $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 国的道路结构，每次旅行团的经过城镇序列是唯一确定的。 你打算参加其中一次旅行团，并正好在旅途中经过的两个城镇各买一件纪念品，并且花费要正好等于你的预算。对于每一个给定的预算 $B_q$，你想知道有多少种方案可以做到这一点。 给定 JOI 国的道路、纪念品价格、旅行团信息以及多个候选预算 $B_1,B_2,\ldots,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.（3 分）$N \leq 100$，$M \leq 100$，$Q \leq 100$。 2.（4 分）$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 分）$N \leq 5\,000$。 4.（6 分）$Q = 1$，$U_j = j$（$1 \leq j \leq N-1$），$V_j = j+1$（$1 \leq j \leq N-1$）。 5.（10 分）$Q = 1$。 6.（7 分）$M \leq 1000$，$U_j = j$（$1 \leq j \leq N-1$），$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$（$1 \leq j \leq N-1$），$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$（$1 \leq j \leq N-1$），$V_j = j+1$（$1 \leq j \leq N-1$）。 11.（17 分）无额外条件。 --- ### 样例解释 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)$。 - 恰好用掉预算 $16$ 的方案有 $0$ 种。 该组输入满足子任务 $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$。 - 所有输入均为整数。 由 ChatGPT 5 翻译