# Description
洛谷传送门
# Solution
重构树好题。
我们先按照水位 ，建 重构树。具体来讲：按水位从高到低排序，每次选出剩余边中水位最高的一条边插入到树中，这样就建成了一个小根堆。
然后我们再来考虑询问。
对于一个水位线 ，若 重构树上的点 的水位，那么在以 为根的子树中，开车是可以随意通行的，对答案没有贡献。
若 且 ，那么它就不得不在点 下车，所以对答案的贡献就是从 到 1 的距离。
那这个距离该如何算呢？
这个很简单，只需要提前跑个 堆优化预处理一下即可，千万千万千万不要使用 （spfa 就是在这里死的 QwQ）
我们对于一组询问 ，找到上述的 节点即可。
现在的问题就是如何找到这样的节点，我们考虑倍增，倍增向上跳（就是个板子），具体见代码。
# Code
（UOJ 不干人事 hack 了 把 0x3f3f3f3f 作为无穷大，而且无穷大开 的话还得开 ，所以这里放个洛谷能过的代码吧。）
#include <bits/stdc++.h> | |
#define INF 0x3f3f3f3f | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 4e5 + 10; | |
int T, n, m, lst; | |
struct node{ | |
int u, v, l, a, nxt; | |
bool operator < (const node &b) const{ | |
return a > b.a; | |
} | |
}edge[N << 1], e[N << 1], tmp[N << 1]; | |
int head[N], tot; | |
inline void add(int x, int y, int l){ | |
edge[++tot].v = y, edge[tot].l = l, edge[tot].nxt = head[x]; | |
head[x] = tot; | |
} | |
struct Heap{ | |
int id, dis; | |
bool operator < (const Heap &b) const{ | |
return dis > b.dis; | |
} | |
}; | |
int dis[N]; | |
inline void dijkstra(){ | |
priority_queue <Heap> q; | |
q.push((Heap){1, 0}); | |
memset(dis, 0x3f, sizeof(dis)); | |
dis[1] = 0; | |
while(!q.empty()){ | |
Heap now = q.top(); | |
q.pop(); | |
int x = now.id; | |
if(dis[x] < now.dis) continue; | |
for(int i = head[x]; i; i = edge[i].nxt){ | |
int y = edge[i].v; | |
if(dis[y] > dis[x] + edge[i].l){ | |
dis[y] = dis[x] + edge[i].l; | |
q.push((Heap){y, dis[y]}); | |
} | |
} | |
} | |
} | |
int f[N]; | |
int cnt; | |
vector <int> g[N]; | |
inline int find(int x){ | |
return f[x] == x ? x : f[x] = find(f[x]); | |
} | |
inline void kruskal(){ | |
sort(e + 1, e + 1 + m); | |
for(int i = 1; i <= n; ++i) f[i] = i; | |
cnt = n; | |
int num = 0; | |
for(int i = 1; i <= m; ++i){ | |
int fu = find(e[i].u), fv = find(e[i].v); | |
if(fu != fv){ | |
num++; | |
tmp[++cnt].a = e[i].a; | |
f[fu] = f[fv] = f[cnt] = cnt; | |
g[cnt].push_back(fu), g[cnt].push_back(fv); | |
} | |
if(num == n - 1) break; | |
} | |
} | |
int fa[N][20], dep[N]; | |
inline void dfs(int x, int p){ | |
fa[x][0] = p, dep[x] = dep[p] + 1; | |
for(int i = 1; i <= 19; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1]; | |
for(auto y : g[x]) | |
dfs(y, x), tmp[x].l = min(tmp[x].l, tmp[y].l); | |
} | |
inline int query(int x, int y){ | |
for(int i = 19; i >= 0; --i) | |
if(dep[x] - (1 << i) > 0 && tmp[fa[x][i]].a > y) | |
x = fa[x][i]; | |
return tmp[x].l; | |
} | |
inline void solve(){ | |
kruskal(); | |
dfs(cnt, 0); | |
int q = read(), k = read(), s = read(); | |
while(q--){ | |
int u = (read() + k * lst - 1) % n + 1, p = (read() + k * lst) % (s + 1); | |
write(lst = query(u, p)), puts(""); | |
} | |
} | |
inline void clear(){ | |
memset(head, 0, sizeof(head)); | |
memset(fa, 0, sizeof(fa)); | |
memset(tmp, 0, sizeof(tmp)); | |
memset(f, 0, sizeof(f)); | |
for(int i = 1; i <= cnt; ++i) g[i].clear(); | |
tot = lst = 0; | |
} | |
int main(){ | |
T = read(); | |
while(T--){ | |
n = read(), m = read(); | |
for(int i = 1; i <= m; ++i){ | |
e[i].u = read(), e[i].v = read(), e[i].l = read(), e[i].a = read(); | |
add(e[i].u, e[i].v, e[i].l), add(e[i].v, e[i].u, e[i].l); | |
} | |
dijkstra(); | |
for(int i = 1; i <= n; ++i) tmp[i].l = dis[i]; | |
for(int i = (n + 1); i <= (n << 1); ++i) tmp[i].l = INF; | |
solve(), clear(); | |
} | |
return 0; | |
} |
