分数: 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.
- 所有输入值均为整数。
子任务
- (3 点) N\leq 100, M\leq 100, Q\leq 100.
- (4 点) N\leq 5\,000, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
- (5 点) N\leq 5\,000.
- (6 点) Q= 1, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
- (10 点) Q= 1.
- (7 点) M\leq 1000, U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
- (12 点) M\leq 1000.
- (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).
- (15 点) N\leq 50\,000, M\leq 50\,000.
- (11 点) U_j=j (1\leq j\leq N-1), V_j=j+1 (1\leq j\leq N-1).
- (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.