归程
格式难调，题面就不放了。
分析：
之前同步赛的时候反正就一脸懵逼，然后场场暴力大战，现在呢，还是不会$Kruskal$重构树，于是就拿可持久化并查集做。
但是之前做可持久化并查集的时候感觉掌握的并不熟，还是需要参照别人的题解，不过至少现在对可持久化的理解更深了一步，而且终于这题给调对了。
Code：
//It is made by HolseLee on 23rd Aug 2018 //Luogu.org 4768 #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define Min(a,b) (a)<(b)?(a):(b) #define Max(a,b) (a)>(b)?(a):(b) using namespace std; const int N=2e5+7,M=8e5+7,S=2e7+1; typedef unsigned int ui; ui T,n,m,Q,K,s,lastans,L,cnt; ui head[N],nxt[M],to[M],d[M],a[M],b[M],dis[N]; ui rt[M],lc[S],rc[S],dep[S],fa[S],mn[S]; bool vis[N]; struct Node{ ui id,val; bool operator < (const Node x) const { return val>x.val; } Node(ui x=0,ui y=0){ id=x,val=y; } }; struct Edge{ ui u,v,h; bool operator < (const Edge x) const { return h<x.h; } Edge(ui x=0,ui y=0,ui z=0){ u=x,v=y,h=z; } }e[M]; priority_queue<Node> t; inline ui read() { char ch=getchar();ui num=0; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){ num=(num<<1)+(num<<3)+(ch^48);ch=getchar(); } return num; } void build(ui &root,ui l,ui r) { root=++cnt; if(l==r){mn[root]=dis[fa[root]=l];return;} ui mid=(l+r)>>1; build(lc[root],l,mid); build(rc[root],mid+1,r); } ui ins(ui *root,ui las,ui tag) { ui l=1,r=n,mid; while(l!=r){ *root=++cnt,mid=(l+r)>>1; if(tag<=mid)r=mid,rc[*root]=rc[las],root=lc+*root,las=lc[las]; else l=mid+1,lc[*root]=lc[las],root=rc+*root,las=rc[las]; } return *root=++cnt; } ui find(ui root,ui tag) { ui now,l,r,mid; while(1){ now=root,l=1,r=n; while(l!=r){ mid=(l+r)>>1; if(tag<=mid)r=mid,now=lc[now]; else l=mid+1,now=rc[now]; } if(tag==fa[now])break; tag=fa[now]; } return now; } int main() { T=read(); ui i,j; while(T--){ n=read();m=read(); ui x,y,w,cnte=0;cnt=0; for(i=1;i<=m;++i){ x=read();y=read(); to[++cnte]=y,nxt[cnte]=head[x],head[x]=cnte; to[++cnte]=x,nxt[cnte]=head[y],head[y]=cnte; d[cnte]=d[cnte-1]=read(); e[i]=Edge(x,y,a[cnte]=a[cnte-1]=read()); } memset(dis,-1,(n+1)<<2); dis[1]=0;t.push(Node(1,0)); while(!t.empty()){ Node now=t.top();t.pop(); if(vis[x=now.id])continue; vis[x]=true; for(i=head[x];i;i=nxt[i]){ y=to[i]; if(dis[y]>dis[x]+d[i]) t.push(Node(y,dis[y]=dis[x]+d[i])); } } Q=read(),K=read(),s=read();lastans=0; sort(e+1,e+m+1); for(i=1;i<=m;++i)b[i]=e[i].h; b[m+1]=s+1; L=unique(b+1,b+m+2)-b-1; build(rt[L],1,n); for(i=L-1,j=m;i;--i){ rt[i]=rt[i+1]; for(;j&&e[j].h==b[i];--j){ if((x=find(rt[i],e[j].u))==(y=find(rt[i],e[j].v)))continue; if(dep[x]>dep[y])swap(x,y); fa[ins(&rt[i],rt[i],fa[x])]=fa[y]; w=ins(&rt[i],rt[i],fa[y]); fa[w]=fa[y];mn[w]=Min(mn[x],mn[y]); dep[w]=dep[y]+(dep[y]==dep[x]); } } for(;Q;--Q){ x=(read()+K*lastans-1)%n+1; y=(read()+K*lastans)%(s+1); printf("%u ",lastans=mn[find(rt[upper_bound(b+1,b+L+1,y)-b],x)]); } memset(vis,0,n+1); memset(head,0,(n+1)<<2); memset(rt,0,(L+1)<<2); memset(lc,0,(cnt+1)<<2); memset(rc,0,(cnt+1)<<2); memset(fa,0,(cnt+1)<<2); memset(mn,0,(cnt+1)<<2); memset(dep,0,(cnt+1)<<2); } return 0; }