求助，请勿无意义回复

QAQ

我比较菜不会kruskal重构树于是写了可持久化并查集

UOJ:http://uoj.ac/submission/411661

Luogu:https://www.luogu.com.cn/record/34916025

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

namespace io {
    const int __SIZE = (1 << 21) + 1;
    char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
    #define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
    inline void gc (char &x) { x = Gc(); }
    inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
    inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
    inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
        for(; __c > 31 && __c < 127 && __c != ' ' && __c != '\n' && __c != '\r'; ++s, __c = Gc()) *s = __c; *s = 0; }
    template <class I> inline bool gi (I &x) { _eof = 0;
        for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
        for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
    template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
        while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}

const int N = 2e5 + 5;
const int M = 4e5 + 5;
const int Q = 4e5 + 5;
int n, m, q, K, S;

struct edge {
	int to, length, height;
	edge(int v, int w, int h) {
		to = v, length = w, height = h;
	}
};
vector<edge> G[N];

int edge_u[M], edge_v[M];
vector<pair<int, int> > height;
/*height & index*/

template<class T>
struct PerArray {
	int lc[N << 5], rc[N << 5];
	int root[M];
	T val[N << 5];
	int timer, total;
	#define mid ((l + r) >> 1)
	int __upd_val(int p, T v, int l, int r, int pre) {
		int x = ++total;
		lc[x] = lc[pre], rc[x] = rc[pre];
		if (l == r) return val[x] = v, x;
		if (p <= mid) lc[x] = __upd_val(p, v, l, mid, lc[pre]);
		else rc[x] = __upd_val(p, v, mid + 1, r, rc[pre]);
		return x;
	}
	T __get_val(int x, int p, int l, int r) {
		if (l == r) return val[x];
		if (p <= mid) return __get_val(lc[x], p, l, mid);
		else return __get_val(rc[x], p, mid + 1, r);
	}
	int __build_tree(int l, int r, T* d) {
		int x = ++total;
		if (l == r) return val[x] = d[l], x;
		lc[x] = __build_tree(l, mid, d);
		rc[x] = __build_tree(mid + 1, r, d);
		return x;
	}
	#undef mid
	
	void update(int p, T v) {
		timer++;
		root[timer] = __upd_val(p, v, 0, n, root[timer - 1]);
	}
	T at(int t, int p) {
		return __get_val(root[t], p, 0, n);
	}
	void copy() {
		root[++timer] = root[timer - 1];
	}
	void init(T* d) {
		root[0] = __build_tree(0, n, d);
	}
	void reset() {
		timer = total = 0;
	}
};

struct PERSISTENT_DSU{
	PerArray<int> p_fa;
	PerArray<long long> p_dis;
	int fa[N], size[N];
	long long dis[N];
	
	int find(int u) {
		return u == fa[u] ? u : find(fa[u]);
	}
	void connect(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return p_fa.copy(), p_dis.copy();
		if (size[u] > size[v]) swap(u, v);
		fa[u] = v, size[v] += size[u], dis[v] = min(dis[v], dis[u]);
		p_fa.update(u, v), p_dis.update(v, dis[v]);
	}
	void init(long long* d) {
		p_fa.reset(), p_dis.reset();
		for (register int i = 1; i <= n; i++) fa[i] = i;
		for (register int i = 1; i <= n; i++) size[i] = 1;
		for (register int i = 1; i <= n; i++) dis[i] = d[i];
		p_fa.init(fa), p_dis.init(dis);
	}
} pdsu;

struct SINGLE_SOURCE_SHORTEST_PATH{
	long long dis[N];
	bool book[N];
	
	struct heapNode {
		int pos;
		long long dis;
		heapNode(int p, long long d) : pos(p), dis(d) { }
		bool operator < (const heapNode& t) const {
			return dis > t.dis;
		}
	};
	priority_queue<heapNode> pq;
	
	void Dijkstra() {
		memset(dis, 0x3f, sizeof dis);
		memset(book, 0, sizeof book);
		while (!pq.empty()) pq.pop();
		
		pq.push(heapNode(1, dis[1] = 0));
		while (!pq.empty()) {
			heapNode x = pq.top();
			pq.pop();
			if (book[x.pos]) continue;
			book[x.pos] = true;
			for (vector<edge>::iterator it = G[x.pos].begin(); it != G[x.pos].end(); it++) {
				int to = it->to, len = it->length;
				if (dis[to] > len + x.dis) {
					dis[to] = len + x.dis;
					pq.push(heapNode(to, dis[to]));
				}
			}
		}
	}
} sssp;

long long query(int v, int p) {
	int time = height.end()
			- upper_bound(height.begin(), height.end(), make_pair(p, 0x3f3f3f3f));
	int pos = v;
	for (register int f; ; ) {
		f = pdsu.p_fa.at(time, pos);
		if (f == pos) break;
		pos = f;
	}
	return pdsu.p_dis.at(time, pos);
}

void solve() {
	io::gi(n), io::gi(m);
	for (register int i = 1; i <= n; i++)
		G[i].clear();
	
	height.clear(), height.resize(m);
	for (register int i = 1; i <= m; i++) {
		int u, v, w;
		io::gi(u), io::gi(v), io::gi(w), io::gi(height[i - 1].first);
		G[u].push_back(edge(v, w, height[i - 1].first));
		G[v].push_back(edge(u, w, height[i - 1].first));
		height[i - 1].second = i;
		edge_u[i] = u, edge_v[i] = v;
	}
	
	sssp.Dijkstra();
	pdsu.init(sssp.dis);
	
	sort(height.begin(), height.end());
	for (register int i = m - 1; ~i; i--)
		pdsu.connect(edge_u[height[i].second], edge_v[height[i].second]);
	
	io::gi(q), io::gi(K), io::gi(S);
	long long last = 0;
 	while (q--) {
		int v, p;
		io::gi(v), io::gi(p);
		v = (v + K * last - 1) % n + 1;
		p = (p + K * last) % (S + 1);
		last = query(v, p);
		io::print(last), io::pc('\n');
	}
}

signed main() {
	int test_case;
	io::gi(test_case);
	
	while (test_case--)
		solve();
	return 0;
}