显然可以持久化并查集。
（我的写法并不好，因为没有路径压缩，其实可以路径压缩。做到O（Nαlog） 。）
#include<bits/stdc++.h> #define Mid (l+r>>1) using namespace std; #define N 200007 #define M 400007 #define eho(x) for(int i=head[x];i;i=net[i]) #define v fall[i] #define fi first #define se second #define inf (INT_MAX>>1) #define sight(x) ('0'<=x&&x<='9') inline void read(int &x){ static char c; for (c=getchar();!sight(c);c=getchar()); for (x=0;sight(c);c=getchar())x=x*10+c-48; } void write(int x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);} inline void writeln(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); } inline void writel(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); } priority_queue<pair<int,int> > Q; int dis[N],head[N],net[M<<1],fall[M<<1],ot,co[M<<1],in[N]; int ls[N*35],rs[N*35],V[N*35],p[N*35],x,tot,n,m,T,last; inline void add(int x,int y,int Co){ fall[++ot]=y; net[ot]=head[x]; head[x]=ot; co[ot]=Co; fall[++ot]=x; net[ot]=head[y]; head[y]=ot; co[ot]=Co; } void spfa(){ memset(dis,121,sizeof dis); dis[1]=0; Q.push(make_pair(0,1)); while (!Q.empty()){ pair<int,int> t=Q.top();Q.pop(); if (-t.fi!=dis[t.se]) continue; x=t.se; eho(x) if (dis[x]+co[i]<dis[v]){ dis[v]=dis[x]+co[i]; Q.push(make_pair(-dis[v],v)); } } } void build(int &k,int l,int r){ if(!k)k=++tot; if(l==r){V[k]=l;p[k]=dis[l]; return;} build(ls[k],l,Mid); build(rs[k],Mid+1,r); } void change(int last,int &now,int l,int r,int pos,int to){ now=++tot; if (l==r) {V[now]=to; p[now]=p[last];return;} ls[now]=ls[last]; rs[now]=rs[last]; p[now]=p[last]; V[now]=V[last]; if (pos<=Mid) change(ls[last],ls[now],l,Mid,pos,to); else change(rs[last],rs[now],Mid+1,r,pos,to); } void Change(int last,int &now,int l,int r,int pos,int to){ now=++tot; if (l==r) {V[now]=V[last];p[now]=to; return;} ls[now]=ls[last]; rs[now]=rs[last]; p[now]=p[last]; V[now]=V[last]; if (pos<=Mid) Change(ls[last],ls[now],l,Mid,pos,to); else Change(rs[last],rs[now],Mid+1,r,pos,to); } int orz; void query(int k,int l,int r,int pos){ if(l==r) {orz=V[k]; return; } if(pos<=Mid) query(ls[k],l,Mid,pos); else query(rs[k],Mid+1,r,pos); } int Query(int k,int l,int r,int pos){ if(l==r)return p[k]; if(pos<=Mid)return Query(ls[k],l,Mid,pos); else return Query(rs[k],Mid+1,r,pos); } int gf(int k,int x){ query(k,1,n,x); if(x==orz)return x; return gf(k,orz); } struct edge{ int x,y,l,a; edge(){} edge(int _x,int _y,int _l,int _a):x(_x),y(_y),l(_l),a(_a){} inline bool operator <(const edge& p)const{ return a==p.a?l>p.l:a>p.a; } }e[M];int siz[N],fx,fy,rt[M],Pp,Qq,k,s,st,op,it; void clear() { last=0; tot=0; ot=0; x=0; memset(head,0,sizeof head); memset(ls,0,sizeof ls); memset(rs,0,sizeof rs); memset(rt,0,sizeof rt); } signed main () { freopen("return.in","r",stdin); freopen("return.out","w",stdout); read(T); while (T--) { clear(); read(n); read(m); for (int i=1;i<=m;i++) read(e[i].x),read(e[i].y), read(e[i].l),read(e[i].a); sort(e+1,e+m+1); for (int i=1;i<=m;i++) add(e[i].x,e[i].y,e[i].l); spfa(); build(rt[0],1,n); for (int i=1;i<=n;i++) siz[i]=1; for (int i=1;i<=m;i++) { fx=gf(rt[i-1],e[i].x); fy=gf(rt[i-1],e[i].y); if (fx==fy) {rt[i]=rt[i-1]; continue;} if (siz[fx]<siz[fy]) swap(fx,fy); Pp=Query(rt[i-1],1,n,fx); Qq=Query(rt[i-1],1,n,fy); change(rt[i-1],rt[i],1,n,fy,fx); if (Pp>Qq) Change(rt[i],rt[i],1,n,fx,Qq); siz[fx]+=siz[fy]; } read(Qq); read(k); read(s); while (Qq--) { read(st); read(op); st=(st+k*last-1)%n+1; op=(op+k*last)%(s+1); it=upper_bound(e+1,e+m+1,edge(0,0,inf,op))-e-1; Pp=gf(rt[it],st); writeln(last=Query(rt[it],1,n,Pp)); } cerr<<tot<<endl; } return 0; }