嘟嘟嘟
敲，要是会kruskal重构树，这题也太水了吧。
真的，我感觉模板题都比这难。
首先用dijkstra求出点1到每一个点的最短路，然后以(a)为关键字把边从大到小排序建出kruskal重构树。这样这棵树就是一个小根堆。
对于每一个询问，从(v)倍增往上跳，直到有一个点(x)满足(a[x] > p)且最小。那么(x)的子树中的所有点(v)都可以走到，令每个点的权值为1到他的最短路，则答案就是(x)子树内权值的最小值。
这个最小值dfs预处理一下就好了。
上午没学kruskal重构树的时候这题上手暴力，50分的(O(n ^ 2logn))暴力dij加上10分树的情况，代码都比这个长……
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 2e5 + 5;
const int N = 19;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, q, K, S, ncnt;
int a[maxn << 1], p[maxn << 1];
struct Node
{
int x, y, w, a;
In bool operator < (const Node& oth)const
{
return a > oth.a;
}
}E[maxn << 1];
struct Edge
{
int nxt, to, w;
}e[maxn << 2];
int head[maxn << 1], ecnt = -1;
In void addEdge(int x, int y, int w)
{
e[++ecnt] = (Edge){head[x], y, w};
head[x] = ecnt;
}
In int Find(int x) {return x == p[x] ? x : p[x] = Find(p[x]);}
#define pr pair<int, int>
#define mp make_pair
bool in[maxn];
int dis[maxn];
In void dijkstra(int s)
{
for(int i = 1; i <= n; ++i) dis[i] = INF, in[i] = 0;
priority_queue<pr, vector<pr>, greater<pr> > q;
q.push(mp(dis[s] = 0, s));
while(!q.empty())
{
int now = q.top().second; q.pop();
if(in[now]) continue;
in[now] = 1;
for(int i = head[now], v; ~i; i = e[i].nxt)
{
if(dis[v = e[i].to] > dis[now] + e[i].w)
{
dis[v] = dis[now] + e[i].w;
q.push(mp(dis[v], v));
}
}
}
}
int dep[maxn << 1], fa[N + 2][maxn << 1], Min[maxn << 1];
In void dfs(int now)
{
Min[now] = now <= n ? dis[now] : INF;
for(int i = 1; (1 << i) <= dep[now]; ++i)
fa[i][now] = fa[i - 1][fa[i - 1][now]];
for(int i = head[now], v; ~i; i = e[i].nxt)
{
dep[v = e[i].to] = dep[now] + 1;
fa[0][v] = now;
dfs(v);
Min[now] = min(Min[now], Min[v]);
}
}
In int solve(int x, int p)
{
for(int i = N; i >= 0; --i)
if(fa[i][x] && a[fa[i][x]] > p) x = fa[i][x];
return x;
}
In void init()
{
Mem(head, -1), ecnt = -1;
Mem(fa, 0), Mem(dep, 0);
for(int i = 1; i <= n; ++i) p[i] = i;
}
int main()
{
freopen("return.in", "r", stdin);
freopen("return.out", "w", stdout);
int T = read();
while(T--)
{
n = read(), m = read();
init();
for(int i = 1; i <= m; ++i)
{
int x = read(), y = read(), w = read(), a = read();
addEdge(x, y, w), addEdge(y, x, w);
E[i] = (Node){x, y, w, a};
}
dijkstra(1);
Mem(head, -1), ecnt = -1;
sort(E + 1, E + m + 1); ncnt = n;
for(int i = 1; i <= m; ++i)
{
int px = Find(E[i].x), py = Find(E[i].y);
if(px == py) continue;
a[++ncnt] = E[i].a;
p[ncnt] = ncnt;
addEdge(ncnt, px, 0), addEdge(ncnt, py, 0);
p[px] = ncnt, p[py] = ncnt;
}
dfs(ncnt);
q = read(), K = read(), S = read();
for(int i = 1, ans = 0; i <= q; ++i)
{
int v = (read() + K * ans - 1) % n + 1;
int p = (read() + K * ans) % (S + 1);
v = solve(v, p);
write(ans = Min[v]), enter;
}
}
return 0;
}