E. Qpwoeirut and Vertices

kruskal重构树模板题

首先有三个等价的性质 我不会证!

图上任意两点的所有路径最大权值的最小值=最小生成树上任意路径的最大值=kruskal树上的lca.

就像不会sam一样 不过这个记着就行.

那么原问题就是按边的编号作为权值,查询两两之间的lca的val,最后用一个可以维护区间最值的数据结构得到答案.

code:

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;
const int M=20;

int cnt=0;
int fa[N],ch[N][2],f[N][M],val[N],dep[N];
int n,m,q;
int w[N],mx[N<<1];
struct node{
	int u,v,w;
}a[N];

void init()
{
	for(int i=0;i<=(n<<1);i++)	fa[i]=i;
}

int dsu(int u)
{
	if(u==fa[u])	return u;
	else			return fa[u]=dsu(fa[u]);
}

void kruskal()
{
	for(int i=1;i<=m;i++)
	{
		int x=dsu(a[i].u);int y=dsu(a[i].v);
		if(x==y)	continue;
		ch[++cnt][0]=x,ch[cnt][1]=y;
		fa[x]=fa[y]=f[x][0]=f[y][0]=cnt;
		val[cnt]=a[i].w;
	}
	for(int i=1;i<20;i++)
		for(int j=1;j<=cnt;j++)
			f[j][i]=f[f[j][i-1]][i-1];
}

void dfs(int u)
{
	dep[u]=dep[f[u][0]]+1;
	if(ch[u][0])	dfs(ch[u][0]);
	if(ch[u][1])	dfs(ch[u][1]);
}

int lca(int u,int v)
{
	if(dep[u]<dep[v])	swap(u,v);
	for(int i=19;i>=0;i--)
	{
		if(dep[f[u][i]]>=dep[v])	u=f[u][i];
	}
	if(u==v)	return u;
	for(int i=19;i>=0;i--)
	{
		if(f[u][i]!=f[v][i])	u=f[u][i],v=f[v][i];
	}
	return f[u][0];
}

void build(int u,int l,int r)
{
	if(l==r)
	{
		mx[u]=w[l];
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	mx[u]=max(mx[u<<1],mx[u<<1|1]);
}

int qry(int u,int l,int r,int L,int R)
{
	if(R<L)			return 0;
	if(R<l||L>r)	return 0;
	if(L<=l&&r<=R)	return mx[u];
	int mid=(l+r)>>1;
	return max(qry(u<<1,l,mid,L,R),qry(u<<1|1,mid+1,r,L,R));
}

void run()
{
	scanf("%d%d%d",&n,&m,&q);
	cnt=n;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		a[i]={u,v,i};
	}
	init();
	kruskal();
	dfs(cnt);
	for(int i=1;i<n;i++)
		w[i]=val[lca(i,i+1)];
	build(1,1,n-1);
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d ",qry(1,1,n-1,l,r-1));
	}
	printf("\n");
}

int main() 
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		run();
	}
	return 0;
}