Spanning Tree Queries
Contest: Educational Codeforces Round 122 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, data structures, dfs and similar, dsu, graphs, greedy, math, sortings, trees

You are given a connected weighted undirected graph, consisting of $$$n$$$ vertices and $$$m$$$ edges.

You are asked $$$k$$$ queries about it. Each query consists of a single integer $$$x$$$. For each query, you select a spanning tree in the graph. Let the weights of its edges be $$$w_1, w_2, \dots, w_{n-1}$$$. The cost of a spanning tree is $$$\sum \limits_{i=1}^{n-1} |w_i - x|$$$ (the sum of absolute differences between the weights and $$$x$$$). The answer to a query is the lowest cost of a spanning tree.

The queries are given in a compressed format. The first $$$p$$$ $$$(1 \le p \le k)$$$ queries $$$q_1, q_2, \dots, q_p$$$ are provided explicitly. For queries from $$$p+1$$$ to $$$k$$$, $$$q_j = (q_{j-1} \cdot a + b) \mod c$$$.

Print the xor of answers to all queries.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 50$$$; $$$n - 1 \le m \le 300$$$) — the number of vertices and the number of edges in the graph.

Each of the next $$$m$$$ lines contains a description of an undirected edge: three integers $$$v$$$, $$$u$$$ and $$$w$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$; $$$0 \le w \le 10^8$$$) — the vertices the edge connects and its weight. Note that there might be multiple edges between a pair of vertices. The edges form a connected graph.

The next line contains five integers $$$p, k, a, b$$$ and $$$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$$$) — the number of queries provided explicitly, the total number of queries and parameters to generate the queries.

The next line contains $$$p$$$ integers $$$q_1, q_2, \dots, q_p$$$ ($$$0 \le q_j < c$$$) — the first $$$p$$$ queries.

Output format:
Print a single integer — the xor of answers to all queries.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
The queries in the first example are $$$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0$$$. The answers are $$$11, 9, 7, 3, 1, 5, 8, 7, 5, 7, 11$$$.

The queries in the second example are $$$3, 0, 2, 1, 6, 0, 3, 5, 4, 1$$$. The answers are $$$14, 19, 15, 16, 11, 19, 14, 12, 13, 16$$$.

The queries in the third example are $$$75, 0, 0, \dots$$$. The answers are $$$50, 150, 150, \dots$$$.

Example input:
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

Example output:
4

Example input:
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

Example output:
5

Editorial:
Consider a naive solution using Kruskal's algorithm for finding MST. Given some $$$x$$$, you arrange the edges in the increasing order of $$$|w_i - x|$$$ and process them one by one.
Look closely at the arrangements. At $$$x=0$$$ the edges are sorted by $$$w_i$$$. How does the arrangement change when $$$x$$$ increases? Well, some edges swap places.
Consider a pair of edges with different weights $$$w_1$$$ and $$$w_2$$$ ($$$w_1 < w_2$$$). Edge $$$1$$$ will go before edge $$$2$$$ in the arrangement as long as $$$x$$$ is closer to $$$w_1$$$ than $$$w_2$$$. So for all $$$x$$$ up to $$$\frac{w_1 + w_2}{2}$$$, edge $$$1$$$ goes before edge $$$2$$$. And for all $$$x$$$ from $$$\frac{w_1 + w_2}{2}$$$ onwards, edge $$$2$$$ goes before edge $$$1$$$.
This tells us that every pair of edge with different weights will swap exactly once. So there will be at most $$$O(m^2)$$$ swaps. Which is at most $$$O(m^2)$$$ different arrangements. Each of them corresponds to some range of $$$x$$$'s.
We can extract the ranges of $$$x$$$'s for all arrangements and calculate MST at the start of each range. We can also find the arrangement that corresponds to some $$$x$$$ from a query with a binary search.
However, only knowing the weight of the MST at the start of the range is not enough. The weights of edges change later in the range, and we can't predict how. Some edges have their weight increasing, some decreasing.
First, let's add more ranges. We want each edge to behave the same way on the entire range: either increase all the way or decrease all the way. If we also add $$$x=w_i$$$ for all $$$i$$$ into the MST calculation, this will hold.
Second, let's store another value for each range: the number of edges that have their weight increasing on it. With that, we can easily recalculate the change in the cost of the spanning tree.
The TL should be free enough for you to sort the edges for each MST calculation, resulting in $$$O(m^2 (m \log m + n \log n) + k \log m)$$$ solution. You can also optimize the first part to $$$O(m^3)$$$.