AdditionalFile5667.zip

#5667. 「JOI 2026 Final Day2」JOI 巡游 2

标签: 传统 | 时间限制: 7000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Final Day2 T2 「JOI ツアー 2 / JOI Tour 2」

JOI 国有 $N$ 个城市，编号为 $1$ 到 $N$。此外，JOI 国有 $N-1$ 条道路，编号为 $1$ 到 $N-1$。道路 $j$ $(1 \le j \le N-1)$ 双向连接城市 $U_j$ 和城市 $V_j$。从任何一个城市出发，都可以通过若干条道路到达任何另一个城市。

JOI 国的每个城市都有一家商店，城市 $i$ $(1 \le i \le N)$ 的商店出售纪念品，价格为 $A_i$。

JOI 国今年计划开展 $M$ 个巡游。第 $k$ $(1 \le k \le M)$ 个巡游从城市 $S_k$ 出发，通过道路移动到城市 $T_k$，且不重复经过同一个城市。也就是说，第 $k$ 个巡游会访问城市 $S_k$ 和 $T_k$ 之间的简单路径上的所有城市。保证 $S_k \neq T_k$。请注意，根据 JOI 国的结构（树形结构），巡游所访问的城市序列是唯一确定的。

你计划参加其中一个巡游，并在访问的城市中恰好选择两个不同的城市各购买一件纪念品。此外，你希望为纪念品准备的预算刚好用完，因此决定针对 $Q$ 种预算候选值，调查每种预算下对应的购买方案有多少种。

给定 JOI 国的道路、纪念品价格、巡游信息以及预算候选值 $B_1, B_2, \ldots, B_Q$，请编写一个程序，计算选择巡游及购买纪念品城市的方法总数。更形式化地，对于每个 $q$ $(1 \le q \le Q)$，求出满足以下所有条件的整数组 $(k, u, v)$ 的个数。

• $1 \le k \le M$。
• $1 \le u < v \le N$。
• 第 $k$ 个巡游访问了城市 $u$ 和 $v$。
• $A_u + A_v = B_q$。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

接下来的 $N-1$ 行，其中第 $j$ 行包含两个整数 $U_j$ 和 $V_j$。

接下来一行包含一个整数 $M$。

接下来的 $M$ 行，其中第 $k$ 行包含两个整数 $S_k$ 和 $T_k$。

接下来一行包含一个整数 $Q$。

最后一行包含 $Q$ 个整数 $B_1, B_2, \ldots, B_Q$。

输出格式

在标准输出中输出 $Q$ 行。第 $q$ $(1 \le q \le Q)$ 行应输出在预算刚好为 $B_q$ 时，选择巡游及购买纪念品城市的方法总数。

样例 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

输出

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

输出

1
2
3
3
1

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

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 100000$。
• $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 200000$。
• $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 2000$。
• $1 \leq B_1 < B_2 < \cdots < B_Q \leq 2N$。
• 所有输入的数值均为整数。

详细子任务附加限制及分值如下表所示。