309158: CF1633E. Spanning Tree Queries
Memory Limit:256 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Spanning Tree Queries
题意翻译
给定一个包含 $n$ 个点和 $m$ 条边的无向带权图,你有 $k$ 次询问,第 $i$ 次询问给定一个整数 $q_i$,你需要从图中选出一棵生成树,设该生成树的 $n-1$ 条边的权值为 $w_1,w_2,\dots,w_{n-1}$,你需要求出 $\sum\limits_{j=1}^{n-1}|w_j-q_i|$ 的最小值。 该题所有 $k$ 次询问中,前 $p$ 次询问的 $q_1,q_2,\dots,q_p$ 在输入中给定,从第 $p+1$ 次询问开始的 $q_i=(q_{i-1}\cdot a+b)\bmod c$。 数据范围: - $2\leqslant n\leqslant 50$,$n-1\leqslant m\leqslant 300$,$1\leqslant p\leqslant 10^5$,$p\leqslant k\leqslant 10^7$,$0\leqslant a,b\leqslant 10^8$,$1\leqslant c\leqslant 10^8$。 - $0\leqslant w_i\leqslant 10^8$。 Translated by Eason_AC 2022.2.2题目描述
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.输入输出格式
输入格式
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.
输出格式
Print a single integer — the xor of answers to all queries.
输入输出样例
输入样例 #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