Description

Input

Output

Sample Input

Sample Output

HINT

Source

LCT维护最小生成树。

题目要求让最大边权最小，那么一定是最小生成树上的边。

往最小生成树上加一条边容易，删一条边难，因此我们把m个操作倒序处理，删边就变成了加边，即判断加上一条边是否比所在环的最大边最小。

怎么用LCT维护最小生成树？

LCT一般都是维护点权的，而最小生成树要求维护边权，因此我们把最小生成树的边权转化成点权：

对于第i条边e[i]，我们连边e[i].x->i+n  e[i].y->i+n，然后把i+n点权赋值为e[i].v,e[i].x e[i].y的点权赋值为0即可。

最后就是LCT的基本操作了，见代码。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define M 2000005
using namespace std;
struct edge
{
	int x,y,v,id,mark;
}e[M];
struct LCT
{
	int rev,l,r,fa,v,ma;
}a[M];
struct Query
{
	int id,k,x,y,ans;
}q[100005];
int n,m,Q,f[M],root[M];
int read()
{
	char ch=getchar();
	for (;ch>'9'||ch<'0';ch=getchar());
	int tmp=0;
	for (;'0'<=ch&&ch<='9';ch=getchar())
		tmp=tmp*10+int(ch)-48;
	return tmp;
}
int Find(int x,int y)
{
	int l=1,r=m;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (e[mid].x<x||(e[mid].x==x&&e[mid].y<y)) l=mid+1;
		else if (e[mid].x==x&&e[mid].y==y) return mid;
		else r=mid-1;
	}
}
bool cmp(edge a,edge b)
{
	return a.v<b.v;
}
bool cmp2(edge a,edge b)
{
	return a.id<b.id;
}
bool cmp3(edge a,edge b)
{
	if (a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
int Getfather(int x)
{
	return x==f[x]?x:f[x]=Getfather(f[x]);
}
void Push_up(int x)
{
	if (!x) return;
	a[x].ma=x;
	int l=a[x].l,r=a[x].r;
	if (a[a[l].ma].v>a[a[x].ma].v) a[x].ma=a[l].ma;
	if (a[a[r].ma].v>a[a[x].ma].v) a[x].ma=a[r].ma;
}
void Push_down(int x)
{
	if (x&&a[x].rev)
	{
		swap(a[x].l,a[x].r);
		a[x].rev=0;
		a[a[x].l].rev^=1,a[a[x].r].rev^=1;
	}
}
void P(int x)
{
	if (!root[x]) P(a[x].fa);
	Push_down(x);
}
void zig(int x)
{
	int y=a[x].fa;
	int z=a[y].fa;
	a[x].fa=z,a[y].fa=x;
	a[y].l=a[x].r,a[a[x].r].fa=y,a[x].r=y;
	if (root[y]) root[y]=0,root[x]=1;
	else
	{
		if (y==a[z].l) a[z].l=x;
		else a[z].r=x;
	}
	Push_up(y);
}
void zag(int x)
{
	int y=a[x].fa;
	int z=a[y].fa;
	a[x].fa=z,a[y].fa=x;
	a[y].r=a[x].l,a[a[x].l].fa=y,a[x].l=y;
	if (root[y]) root[y]=0,root[x]=1;
	else
	{
		if (y==a[z].l) a[z].l=x;
		else a[z].r=x;
	}
	Push_up(y);
}
void Splay(int x)
{
	P(x);
	while (!root[x])
	{
		int y=a[x].fa;
		int z=a[y].fa;
		if (root[y])
		{
			if (x==a[y].l) zig(x);
			else zag(x);
			break;
		}
		if (a[z].l==y)
		{
			if (a[y].l==x) zig(y),zig(x);
			else zag(x),zig(x);
		}
		else
		{
			if (a[y].r==x) zag(y),zag(x);
			else zig(x),zag(x);
		}
	}
	Push_up(x);
}
void Access(int x)
{
	int y=0;
	while (x)
	{
		Splay(x);
		root[a[x].r]=1;
		a[x].r=y;
		root[a[x].r]=0;
		Push_up(x);
		y=x;
		x=a[x].fa;
	}
}
void Makeroot(int x)
{
	Access(x);
	Splay(x);
	a[x].rev^=1;
}
void Link(int x,int y)
{
	Makeroot(x);
	a[x].fa=y;
}
void Cut(int x,int y)
{
	Makeroot(x);
	Access(y),Splay(y);
	root[a[y].l]=1;
	a[a[y].l].fa=0;
	a[y].l=0;
	Push_up(y);
}
int Query(int x,int y)
{
	Makeroot(x);
	Access(y),Splay(y);
	return a[y].ma;
}
int main()
{
        n=read(),m=read(),Q=read();
	for (int i=1;i<=m;i++)
	{
		e[i].x=read(),e[i].y=read(),e[i].v=read();
		if (e[i].x>e[i].y) swap(e[i].x,e[i].y);
	}
	sort(e+1,e+1+m,cmp);
	for (int i=0;i<=m+n;i++)
		a[i].fa=a[i].l=a[i].r=a[i].rev=0,root[i]=1,f[i]=i;
	for (int i=1;i<=m;i++)
	{
		e[i].id=i;
		a[n+i].v=e[i].v;
		a[n+i].ma=n+i;
	}
	sort(e+1,e+1+m,cmp3);  
	for (int i=1;i<=Q;i++)
	{
		q[i].k=read(),q[i].x=read(),q[i].y=read();
		if (q[i].x>q[i].y) swap(q[i].x,q[i].y);
		if (q[i].k==2)
		{
			int t=Find(q[i].x,q[i].y);
			e[t].mark=1;
			q[i].id=e[t].id;
		}
	}
	sort(e+1,e+1+m,cmp2);
	int tot=0;
	for (int i=1;i<=m;i++)
		if (!e[i].mark)
		{
			int x=e[i].x,y=e[i].y,f1=Getfather(x),f2=Getfather(y);
			if (f1!=f2)
			{
				f[x]=y;
				Link(x,i+n),Link(y,i+n);
				tot++;
				if (tot==n-1) break;
			}
		}
	for (int i=Q;i;i--)
	{
		if (q[i].k==1)
			q[i].ans=a[Query(q[i].x,q[i].y)].v;
		else
		{
			int x=q[i].x,y=q[i].y,k=q[i].id;
			int t=Query(x,y);
			if (e[k].v<a[t].v)
			{
				Cut(e[t-n].y,t),Cut(e[t-n].x,t);
				Link(x,k+n),Link(y,k+n);
			}
		}
	}
	for (int i=1;i<=Q;i++)
		if (q[i].k==1)
			printf("%d\n",q[i].ans);
	return 0;
}

感悟：

1.一开始一直RE，因为LCT上有m+n个点；

Cut完要Push_up一下；

Splay过程中要Push_up

2.拆边为点，用LCT维护最小生成树很巧妙~

【BZOJ 2594】 [Wc2006]水管局长数据加强版