可持久化并查集做法

#include<bits/stdc++.h>
using namespace std;
const int N=8e5+100,M=3e6+100;
const int inf=2e9+100;
#define re register
int n,m,Q,K,S,dis[N];
int head[N],to[N],w[N],ne[N],tot;
void add(int x,int y,int z){
	ne[++tot]=head[x];
	to[tot]=y,w[tot]=z;
	head[x]=tot;
}
bool vis[N];
struct node{
	int id,dis;
	bool operator <(node it)const{
		return dis>it.dis;
	}
};priority_queue<node>q;
struct edge{int u,v,l,a;}e[N];
bool cmp(edge A,edge B){return A.a>B.a;}
void dij(){
	dis[1]=0;
	q.push((node){1,0});
	while(!q.empty()){
		node u=q.top();q.pop();
		if(vis[u.id]) continue;
		vis[u.id]=1;
		for(re int i=head[u.id];i;i=ne[i]){
			int v=to[i];
			if(dis[v]>u.dis+w[i]){
				dis[v]=u.dis+w[i];
				q.push((node){v,dis[v]});
			}
		}
	}
}
int cnt,rtf[N],rtde[N],rti[N];
struct tree{int l,r,val;}t[M]; 
inline void build(int &i,int l,int r){
	i=++cnt;
	if(l==r) return void(t[i].val=l);
	int mid=(l+r)>>1;
	build(t[i].l,l,mid),build(t[i].r,mid+1,r);
}
inline void build_mi(int &i,int l,int r){
	i=++cnt;
	if(l==r) return void(t[i].val=dis[l]);
	int mid=(l+r)>>1;
	build_mi(t[i].l,l,mid),build_mi(t[i].r,mid+1,r);
}
inline void build_de(int &i,int l,int r){
	i=++cnt;
	if(l==r) return void(t[i].val=0);
	int mid=(l+r)>>1;
	build_de(t[i].l,l,mid),build_de(t[i].r,mid+1,r);
}
inline void update(int &i,int j,int l,int r,int pos,int val){
	i=++cnt;
	t[i]=t[j];
	if(l==r) return void(t[i].val=val);
	int mid=(l+r)>>1;
	if(pos<=mid) update(t[i].l,t[j].l,l,mid,pos,val);
	else update(t[i].r,t[j].r,mid+1,r,pos,val);
}
inline int query(int i,int l,int r,int pos){
	if(l==r) return t[i].val;
	int mid=(l+r)>>1;
	if(pos<=mid) return query(t[i].l,l,mid,pos);
	else return query(t[i].r,mid+1,r,pos);
}
inline int find(int i,int x){
	int fx=query(rtf[i],1,n,x);
	return fx==x?x:find(i,fx);	
}
inline void merge(int i,int x,int y){
	x=find(i-1,x),y=find(i-1,y);
	if(x==y) rtf[i]=rtf[i-1],rtde[i]=rtde[i-1],rti[i]=rti[i-1];
	else{
		int mix=query(rti[i-1],1,n,x),miy=query(rti[i-1],1,n,y);
		int dex=query(rtde[i-1],1,n,x),dey=query(rtde[i-1],1,n,y);
		if(dex<dey){
			update(rtf[i],rtf[i-1],1,n,x,y),rtde[i]=rtde[i-1];
			if(mix<miy) update(rti[i],rti[i-1],1,n,y,mix);
			else rti[i]=rti[i-1];
		}
		else if(dex>dey){
			update(rtf[i],rtf[i-1],1,n,y,x),rtde[i]=rtde[i-1];
			if(miy<mix) update(rti[i],rti[i-1],1,n,x,miy);
			else rti[i]=rti[i-1];
		}
		else{
			update(rtf[i],rtf[i-1],1,n,x,y),update(rtde[i],rtde[i-1],1,n,y,dey+1);
			if(mix<miy) update(rti[i],rti[i-1],1,n,y,mix);
			else rti[i]=rti[i-1];	
		}
	}
}
void deal(){
	for(re int i=1;i<=n;i++) head[i]=vis[i]=0,dis[i]=inf;
	cnt=tot=0;
}
void work(){
	cin>>n>>m;	
	deal();
	for(int i=1;i<=m;i++) scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].a),add(e[i].u,e[i].v,e[i].l),add(e[i].v,e[i].u,e[i].l);
	cin>>Q>>K>>S;
	dij();
	build(rtf[0],1,n),build_mi(rti[0],1,n),build_de(rtde[0],1,n);
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++) merge(i,e[i].u,e[i].v);
	int last_ans=0;
	while(Q--){
		int v0,p0;
		scanf("%d%d",&v0,&p0);
		int v=(v0+K*last_ans-1)%n+1;
		int p=(p0+K*last_ans)%(S+1);
		int l=1,r=m,pos=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(e[mid].a>p) l=mid+1,pos=mid;
			else r=mid-1;
		}
		last_ans=query(rti[pos],1,n,find(pos,v));
		cout<<last_ans<<endl;
	}
}
signed main(){
	int T;cin>>T;
	while(T--) work();
}