← 返回题目列表

Codeforces · 1633/E

E. 生成树查询

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

给您一个连接的加权无向图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。

系统会向您询问 $$$k$$$ 相关问题。每个查询由一个整数 $$$x$$$ 组成。对于每个查询,您在图中选择一棵生成树。设其边的权重为$$$w_1, w_2, \dots, w_{n-1}$$$。生成树的成本为 $$$\sum \limits_{i=1}^{n-1} |w_i - x|$$$ (权重与 $$$x$$$ 之间的绝对差之和)。查询的答案是生成树的最低成本。

查询以压缩格式给出。第一个 $$$p$$$ $$$(1 \le p \le k)$$$ 查询 $$$q_1, q_2, \dots, q_p$$$ 是明确提供的。对于从 $$$p+1$$$ 到 $$$k$$$ 的查询,$$$q_j = (q_{j-1} \cdot a + b) \mod c$$$。

打印所有查询答案的异或。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 50$$$; $$$n - 1 \le m \le 300$$$) - 图中的顶点数和边数。

接下来的 $$$m$$$ 行包含无向边的描述:三个整数 $$$v$$$、$$$u$$$ 和 $$$w$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$; $$$0 \le w \le 10^8$$$) - 边连接的顶点它的重量。请注意,一对顶点之间可能存在多条边。边形成连通图。

下一行包含五个整数 $$$p、k、a、b$$$ 和 $$$c$$$ ($$$1 \le p \le 10^5$$$; $$$p \le k \le 10^7$$$; $$$0 \le a, b \le 10^8$$$; $$$1 \le c \le 10^8$$$) —显式提供的查询数量、查询总数以及生成查询的参数。

下一行包含 $$$p$$$ 整数 $$$q_1, q_2, \dots, q_p$$$ ($$$0 \le q_j < c$$$) — 第一个 $$$p$$$ 查询。

输出

打印一个整数——所有查询答案的异或。

示例

输入 #1

5 8
4 1 4
3 1 0
3 5 3
2 5 4
3 4 8
4 3 4
4 2 8
5 3 9
3 11 1 1 10
0 1 2

输出 #1

4

输入 #2

6 7
2 4 0
5 4 7
2 4 0
2 1 7
2 6 1
3 4 4
1 4 8
4 10 3 3 7
3 0 2 1

输出 #2

5

输入 #3

3 3
1 2 50
2 3 100
1 3 150
1 10000000 0 0 100000000
75

输出 #3

164

注意

第一个示例中的查询为 $$$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0$$$。答案是 $$$11, 9, 7, 3, 1, 5, 8, 7, 5, 7, 11$$$。

第二个示例中的查询为 $$$3, 0, 2, 1, 6, 0, 3, 5, 4, 1$$$。答案是 $$$14, 19, 15, 16, 11, 19, 14, 12, 13, 16$$$。

第三个示例中的查询是 $$$75, 0, 0, \dots$$$。答案是 $$$50、150、150、\dots$$$。