RT

luogu在线ide可过下载的数据（时间空间ok答案正确）

提交MLE

（经测试，并不是空间开爆的原因）

求解答

（我校oj可过）

#include<bits/stdc++.h>
using namespace std;
int read()
{
	char c;
	int w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	int ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
int n,m,q;
int cstw;
int ans[300005];
struct node
{
	int a,b,c;
}e[2000005];
int fa[300005];
int findf(int x)
{
	return fa[x]==x?x:fa[x]=findf(fa[x]);
}
map <pair<int,int>,int> mm;
int w[300005][4];
bool cmp(node x,node y)
{
	return x.c<y.c;
}
int size[300005];
int maxx[300005][2];
int c[300005][2];
int val[300005];
int uu[300005];
int vv[300005];
int rev[300005];
int f[300005];
void ph(int x)
{
	maxx[x][0]=val[x];
	maxx[x][1]=x;
	if(maxx[c[x][0]][0]>maxx[x][0])
	{
		maxx[x][0]=maxx[c[x][0]][0];
		maxx[x][1]=maxx[c[x][0]][1];
	}
	if(maxx[c[x][1]][0]>maxx[x][0])
	{
		maxx[x][0]=maxx[c[x][1]][0];
		maxx[x][1]=maxx[c[x][1]][1];
	}
}
bool nroot(int x)
{
	return (c[f[x]][0]==x)||(c[f[x]][1]==x);
}
void rotate(int x)
{
	int fa=f[x],gr=f[fa],s=c[fa][1]==x;
	c[fa][s]=c[x][!s];f[c[x][!s]]=fa;
	f[x]=gr;if(nroot(fa))c[gr][c[gr][1]==fa]=x;
	f[c[x][!s]=fa]=x;ph(fa);ph(x);
}
int rv(int x)
{
	if(x)swap(c[x][0],c[x][1]),rev[x]^=1;
}
void pd(int x)
{
	if(rev[x])rv(c[x][0]),rv(c[x][1]),rev[x]=0;
}
void pds(int x)
{
	if(nroot(x))pds(f[x]);
	pd(x);
}
void print(int x)
{
	if(!x)return;
	pd(x);
	cout<<"QWQ  "<<x<<" ";
	print(c[x][0]);
	print(c[x][1]);
}
void splay(int x)
{
//	cout<<"splay"<<" "<<x<<endl;
	pds(x);
	while(nroot(x))
	{
		int y=f[x];
		int z=f[y];
		if(nroot(y))
		if((c[z][1]==y)==(c[y][1]==x))rotate(y);
		else rotate(x);
		rotate(x);
	}
//			cout<<endl;
//			print(x);
}
void access(int x)
{
	for(int y=0;x;x=f[y=x])
	{
//		cout<<"OOO"<<x<<" "<<endl;
		splay(x);
		c[x][1]=y;
		ph(x);
	}
}
void evert(int x)
{
	access(x);
	splay(x);
	rv(x);
//	print(x);
}
void link(int x,int y)
{
	evert(x);
	f[x]=y;
}
void cut(int x,int y)
{
	evert(x);
	access(y);
	splay(x);
//	cout<<"********************"<<endl;
//	cout<<x<<" "<<y<<" "<<c[x][1]<<' '<<f[y]<<endl;
//	cout<<"********************"<<endl;
	f[y]=c[x][1]=0;
}
int main(){
//	system("fc P4172_2.out b.out");
//	freopen("P4172_2.in","r",stdin);
//	freopen("b.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	m=read();
	q=read();
	int sum=0;
	for(int i=1;i<=m;i++)
	{
		e[i].a=read();
		e[i].b=read();
		if(e[i].a>e[i].b)swap(e[i].a,e[i].b);
		e[i].c=read();
		mm[make_pair(e[i].a,e[i].b)]=i;
	}
	for(int i=1;i<=q;i++)
	{
		w[i][0]=read();
		w[i][1]=read();
		w[i][2]=read();
		if(w[i][1]>w[i][2])swap(w[i][1],w[i][2]);
		if(w[i][0]==2)
		{
			int www=mm[make_pair(w[i][1],w[i][2])];
			w[i][3]=e[www].c;
			e[www].a=0;
			e[www].b=0;
			e[www].c=0;
		}
	}
	sort(e+1,e+m+1,cmp);
	int cnts=n;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		a=e[i].a;
		b=e[i].b;
		c=e[i].c;
//		cout<<c<<endl;
		if(e[i].a==e[i].b&&e[i].a==0)
		{
			continue;
		}
		a=findf(a);
		b=findf(b);
		if(a!=b)
		{
			sum++;
			fa[b]=a;
			++cnts;
//			cout<<e[i].a<<" "<<e[i].b<<" "<<e[i].c<<endl;
			uu[cnts]=e[i].a;
			vv[cnts]=e[i].b;
//			cout<<"-------------------"<<endl;
//			cout<<cnts<<endl;
//			cout<<uu[cnts]<<" "<<vv[cnts]<<endl;
//			cout<<"-------------------"<<endl;
			val[cnts]=e[i].c;
			link(cnts,e[i].a);
			link(e[i].b,cnts);
		}
		if(sum==n-1)break;
	}
	for(int i=q;i>=1;i--)
	{
//		cout<<w[i][0]<<" "<<w[i][1]<<" "<<w[i][2]<<" "<<w[i][3]<<endl;
		if(w[i][0]==2)
		{
			int a,b,c;
			a=w[i][1];
			b=w[i][2];
			c=w[i][3];
			evert(a);
			access(b);
			splay(b);
			if(maxx[b][0]>c)
			{
//				cout<<"qweqweoiwqueowq"<<endl;
//				cout<<maxx[b][0]<<endl;
//cout<<maxx[b][1]<<uu[maxx[b][1]]<<endl;
				int oo=maxx[b][1];
				
				cut(oo,uu[oo]);
				cut(oo,vv[oo]);
				++cnts;
				uu[cnts]=a;
				vv[cnts]=b;
				val[cnts]=c;
//				cout<<"-------------------"<<endl;
//				cout<<cnts<<endl;
//				cout<<uu[cnts]<<" "<<vv[cnts]<<endl;
//				cout<<"-------------------"<<endl;
//				cout<<a<<" "<<b<<" "<<c<<endl;
				link(a,cnts);
				link(b,cnts);
				evert(a);
				access(b);
				splay(b);
//				cout<<maxx[b][0]<<endl;
			}
		}
		if(w[i][0]==1)
		{
			int a,b;
			a=w[i][1];
			b=w[i][2];
			evert(a);
			access(b);
			splay(b);
//			cout<<c[b][0]<<endl;
//			cout<<c[b][1]<<endl;
			ans[++cstw]=maxx[b][0];
//			cout<<b<<" "<<maxx[b][0]<<" "<<cstw<<endl;
		}
//		for(int i=1;i<=6;i++)
//		{
//			cout<<c[i][0]<<" "<<c[i][1]<<endl;
//			cout<<i<<" fi "<<f[i]<<endl;
//			cout<<maxx[i][0]<<" "<<maxx[i][1]<<endl;
//			cout<<val[i]<<endl;
//		}
	}
	for(int i=cstw;i>=1;i--)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}