[NOI2018]归程（Kruskal重构树/可持久化并查集）

洛谷题目传送门

题目描述

给定一个n个点m条边的无向图，每条边有高度和长度，Q次询问，每次给定起点，以及限制高度，求从起点能通过高度大于限制高度的边到达的点中，到1号点最短路的最小值
强制在线

65pts 不强制在线

把边权和询问的权值都排序，用并查集维护连通块内到1号点距离最小的点

100pts

解法一

在65pts上改进
我们只需要把用并查集合并的过程可持久化，就能访问任何一个版本的并查集
就可以做到在线了
若果使用按秩合并的并查集$O(nlo{g}^{2}n)$

解法二

建出Kruskal重构树
那么可以到达的点就是一个子树，用树上倍增维护最远能走到那个点
预处理每个点的子树内到1号店距离最近的点即可
时间复杂度都是$O(nlogn)$，且细节比较少，空间消耗小

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+3;
struct P
{
    
	int id;
	LL v;
};
bool operator <(const P &x,const P &y)
{
    
	return x.v>y.v;
}
priority_queue<P> q;
struct node
{
    
	int y,next,l;
}e[4*N];
struct edge
{
    
	int x,y,h;
}E[2*N]; 
int link[N],t;
int n,m,Q,K,s;
void Insert(int x,int y,int l)
{
    
	e[++t].y=y;
	e[t].l=l;
	e[t].next=link[x];
	link[x]=t;
}
bool cmp(edge a,edge b)
{
    
	return a.h>b.h;
}
int read(){
    
	int ans=0,op=1;char ch=getchar();
	while(ch>'9'||ch<'0'){
    if(ch=='-') op=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
    ans=(ans<<1)+(ans<<3)+ch-'0';ch=getchar();}
	return ans*op;
}
bool vis[N];
LL dis[N];
P Pc(int x,LL v)
{
    
	P tem;
	tem.id=x;
	tem.v=v;
	return tem; 
} 
void dijistra()
{
    
	for(int i=1;i<=n;i++)
	{
    
		vis[i]=0;
		dis[i]=1e15;
	}
	dis[1]=0;
	q.push(Pc(1,0));
	while(!q.empty())
	{
    
		P tp=q.top();q.pop();
		int x=tp.id;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=link[x];i;i=e[i].next)
		{
    
			int y=e[i].y;
// cout<<x<<' '<<y<<' '<<dis[x]<<' '<<e[i].l<<' '<<dis[y]<<endl;
			if(dis[x]+e[i].l<dis[y])
			{
    
				dis[y]=dis[x]+e[i].l;
				q.push(Pc(y,dis[y])); 
			}
		}
	}
}	
int cnt,f[2*N],val[2*N],Min[2*N];
int Find(int x)
{
    
	if(x==f[x]) return x;
	return f[x]=Find(f[x]);
}
int up[2*N][30];
void kruskal()
{
    
	for(int i=1;i<=n;i++)
	{
    
		Min[i]=dis[i];	
		f[i]=i;
	}
	sort(E+1,E+m+1,cmp);
	memset(link,0,sizeof(link));
	t=0;
	for(int i=1;i<=m;i++)
	{
    
		int x=E[i].x;
		int y=E[i].y;
		int fx=Find(x),fy=Find(y);
		if(fx==fy) continue;
		cnt++;
		val[cnt]=E[i].h;
		Min[cnt]=min(Min[fx],Min[fy]);
		f[fx]=cnt;f[cnt]=cnt;f[fy]=cnt;
		up[fx][0]=cnt;
		up[fy][0]=cnt;
		Insert(cnt,fx,0);
		Insert(cnt,fy,0);
	}
}

int main()
{
    
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
	{
    		
		t=0;

		memset(link,0,sizeof(link));
		memset(vis,0,sizeof(vis));
		memset(Min,89,sizeof(Min));
		memset(up,0,sizeof(up));
		n=read();m=read();		cnt=n;
		for(int i=1;i<=m;i++)
		{
    
			int x,y,l,h;
			x=read();
			y=read();
			l=read();
			h=read();
			Insert(x,y,l);
			Insert(y,x,l);
			E[i].x=x;
			E[i].y=y;
			E[i].h=h;
		}
		dijistra();
		kruskal();
		for(int k=1;(1<<k)<=cnt;k++) 
			for(int i=1;i<=cnt;i++) 
				up[i][k]=up[up[i][k-1]][k-1];
		Q=read();K=read();s=read();
		LL last=0;
		while(Q--)
		{
    
			int v0,h0;
			v0=read();
			h0=read();
			int v=(v0+K*last-1)%n+1;
			int h=(h0+K*last)%(s+1); 
			for(int k=22;k>=0;k--)
				if(up[v][k]&&val[up[v][k]]>h) 
					v=up[v][k];
			last=Min[v];
			printf("%lld\n",Min[v]);
		}		
	} 

	return 0;
}