#215994. [JOI Final 2026] JOI 之旅 2 / JOI Tour 2

JOI 国有 个城镇，编号为 到 。此外，JOI 国有 条道路，编号为 到 。道路 () 双向连接城镇 和城镇 。可以通过若干条道路从任意城镇前往任意其他城镇。

JOI 国的每个城镇都有一家商店。在城镇 () 的商店中，一件纪念品的售价为 。

今年，JOI 国计划了 次旅行。第 次旅行 () 从城镇 出发，沿着道路前往城镇 ，且不重复经过同一个城镇。注意，第 次旅行同时访问城镇 和 。保证 。注意，根据 JOI 国的结构，一次旅行所经过的城镇序列是唯一确定的。

你计划参加其中一次旅行，并在该旅行经过的城镇中恰好选出两个，在每个城镇各买一件纪念品。此外，你希望恰好用完为纪念品准备的全部预算，因此对于 个候选预算中的每一个，你决定调查有多少种实现方式。

给定 JOI 国的道路、纪念品价格、旅行信息以及候选预算 ，编写一个程序，计算选择旅行和购买纪念品的城镇的方案数。更确切地说，对于每个 ()，计算满足以下所有条件的整数三元组 的数量：

• 。
• 。
• 第 次旅行访问了城镇 和 。
• 。

从标准输入读取以下数据：

输出 行到标准输出。第 行 () 应包含选择旅行和购买纪念品的城镇的方案数，使得预算 恰好被用完。

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

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

首先，每次旅行访问的城镇如下：

• 第 1 次旅行访问城镇 。
• 第 2 次旅行访问城镇 。
• 第 3 次旅行访问城镇 。
• 第 4 次旅行访问城镇 。

用 表示参加第 次旅行并在城镇 和 购买纪念品的方法。那么，对于每个候选预算，恰好用完预算的方案如下：

• 预算为 时，有 种方案。
• 预算为 时，有 种方案。
• 预算为 时，有 种方案：, , , 。
• 预算为 时，有 种方案：, 。
• 预算为 时，有 种方案：, , , 。
• 预算为 时，有 种方案：。

该输入样例满足子任务 的限制。

样例 2

该输入样例满足子任务 的限制。

限制

• 。
• ()。
• ()。
• ()。
• 可以通过若干条道路从任意城镇前往任意其他城镇。
• 。
• ()。
• ()。
• ()。
• 。
• 。
• 所有输入值均为整数。

子任务

1. (3 分) 。
2. (4 分) ()。
3. (5 分) 。
4. (6 分) ()。
5. (10 分) 。
6. (7 分) ()。
7. (12 分) 。
8. (10 分) ()。
9. (15 分) 。
10. (11 分) ()。
11. (17 分) 无附加限制。