← 返回题目列表

AtCoder · joi2026final_e

E. JOI 巡演 2 (JOI 巡演 2)

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

有 N JOI 国家的城镇,编号为 1 to N。 另外,还有 N-1 JOI 国家的道路,编号为 1 to N-1。 道路 j (1 \leq j \leq N-1) 连接城镇 U_j 和镇 V_j 两个方向。 可以使用一定数量的道路从任何城镇前往任何其他城镇。

JOI国家的每个城镇都有一家商店。 在镇上的商店里 i (1 \leq i \leq N),纪念品以价格出售 A_i.

今年, M 计划在 JOI 国家进行巡演。 的 k第 次巡演 (1 \leq k \leq M) 从城镇出发 S_k 并通过公路前往城镇 T_k 无需访问同一个城镇两次。 请注意, k第 1 次游览参观这两个城镇 S_k 和 T_k。 可以保证 S_k \neq T_k。 需要注意的是,从JOI的国家结构来看,旅行所访问的城镇的顺序是唯一确定的。

您计划参加其中一项旅行,并在旅行中参观的两个城镇中各购买一份纪念品。 此外,您想用完为纪念品准备的全部预算,因此对于每个 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第3次参观城镇 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 正好用完。


约束

  • 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 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

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

首先,每个旅行团参观的城镇如下。

  • 的 1st游览小镇 1, 2, 3, 4.
  • 的 2nd旅游团参观城镇 1, 6.
  • 的 3rd旅游走访城镇 2, 5.
  • 的 4第3次旅游参观城镇 3, 7, 8.

代表参与方法 k城镇游览和购买纪念品 u 和 v by (k,u,v)。 那么,对于每一个候选预算,具体使用预算的方式如下。

  • 有 0 用完预算的方法 1.
  • 有 0 用完预算的方法 2.
  • 有 4 用完预算的方法 3: (1,1,2), (1,1,4), (2,1,6), (3,2,5).
  • 有 2 用完预算的方法 4: (1,1,3), (1,2,4).
  • 有 4 用完预算的方法 5: (1,2,3), (1,3,4), (4,3,8), (4,7,8).
  • 有 1 预算使用方式 6: (4,3,7).
  • 有 0 用完预算的方法 16.

该输入示例满足子任务的约束 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.