E. Spanning Tree Queries
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 w1,w2,…,wn−1. The cost of a spanning tree is ∑i=1n−1|wi−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≤p≤k) queries q1,q2,…,qp are
provided explicitly. For queries from p+1 to k, qj=(qj−1⋅a+b)modc.
Print the xor of answers to all queries.
Input
The first line contains two integers n and m (2≤n≤50; n−1≤m≤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≤v,u≤n; v≠u; 0≤w≤108) — 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≤p≤105; p≤k≤107; 0≤a,b≤108; 1≤c≤108) — the number of queries provided explicitly, the total number of
queries and parameters to generate the queries.
The next line contains p integers q1,q2,…,qp (0≤qj<c) — the first p queries.
Output
Print a single integer — the xor of answers to all queries.
No comments:
Post a Comment