校内oj把n放到了1e5，实在卡不过去了

目前已经用上了unordered_map、40多行的火车头、并查集、fread

附上最开始没卡常的代码

#include<map>
#include<cmath>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAX 100005
#define MAXM 1000005

map<pair<int,int>,int> mp;
int n,m,q,cnt,tot,ans[MAX],fa[MAX],askopt[MAX],askx[MAX],asky[MAX],edgex[MAXM],edgey[MAXM],edgew[MAXM];

struct LCT{
	#define MAXN 1100005

	bool flag[MAXN];
	int top,fa[MAXN],id[MAXN],sta[MAXN],val[MAXN],ch[MAXN][2];

	inline int get(int x){return ch[fa[x]][1]==x;}

	inline void reverse(int x){swap(ch[x][1],ch[x][0]);flag[x]^=1;}

	inline void clear(int x){fa[x]=id[x]=val[x]=ch[x][1]=ch[x][0]=0;}

	inline bool nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}

	inline void push_down(int x){
		if(flag[x]){reverse(ch[x][0]);reverse(ch[x][1]);}
		flag[x]=0;
	}

	inline void push_up(int x){
		clear(0);id[x]=x;
		if(val[id[ch[x][0]]]>val[id[x]]) id[x]=id[ch[x][0]];
		if(val[id[ch[x][1]]]>val[id[x]]) id[x]=id[ch[x][1]];
	}

	inline void rotate(int x){
		int y=fa[x],z=fa[y],k=get(x);
		push_down(y);push_down(x);
		fa[ch[y][k]=ch[x][k^1]]=y;
		if(nroot(y)) ch[z][get(y)]=x;
		fa[x]=z;fa[ch[x][k^1]=y]=x;
		push_up(y);push_up(x);push_up(z);
	}

	inline void splay(int x){
		int y=x;
		sta[top=1]=y;
		while(nroot(y)) sta[++top]=y=fa[y];
		while(top) push_down(sta[top]),top--;
		while(nroot(x)){
			y=fa[x];
			if(nroot(y)) (get(x)==get(y))?rotate(y):rotate(x);
			rotate(x);
		}
		push_up(x);
	}

	inline void access(int x){for(int y=0;x;x=fa[y=x]) splay(x),ch[x][1]=y,push_up(x);}

	inline void makeroot(int x){access(x);splay(x);reverse(x);}

	inline int findroot(int x){
		access(x);splay(x);
		while(ch[x][0]) push_down(x),x=ch[x][0];
		splay(x);
		return x;
	}

	inline void link(int x,int y){
		makeroot(x);
		if(findroot(y)!=x) fa[x]=y;
	}

	inline void spilt(int x,int y){makeroot(x);access(y);splay(x);}

	inline void cut(int x,int y){
		makeroot(x);
		if(findroot(y)==x&&fa[y]==x&&!ch[y][0]) fa[y]=ch[x][1]=0,push_up(x);
	}
}lct;

inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^'0');ch=getchar();}
	return x*f;
}

inline int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}

inline void link(int i){
	//printf("---%d %d %d\n",x,y,w)
	int x=edgex[i],y=edgey[i],w=edgew[i];
	int r1=find(x),r2=find(y);
	if(r1!=r2){
		fa[r1]=r2;
		lct.val[i+n]=w;
		lct.link(x,i+n);lct.link(i+n,y);
	}
	else{
		lct.spilt(x,y);
		int pos=lct.id[x];
		if(edgew[pos-n]>w){
			lct.val[i+n]=w;
			lct.cut(edgex[pos-n],pos);lct.cut(edgey[pos-n],pos);
			lct.link(x,i+n);lct.link(y,i+n);
		}
	}
}

int main(){
	n=cnt=read();m=read();q=read();
	for(int i=1;i<=n;++i) fa[i]=i;
	for(int i=1;i<=m;++i){
		edgex[i]=read(),edgey[i]=read(),edgew[i]=read();
		if(edgex[i]>edgey[i]) swap(edgex[i],edgey[i]);
	}
	for(int i=1;i<=q;++i){
		askopt[i]=read();
		askx[i]=read(),asky[i]=read();
		if(askx[i]>asky[i]) swap(askx[i],asky[i]);
		if(askopt[i]==2) mp[make_pair(askx[i],asky[i])]=i;
	}
	for(int i=1;i<=m;++i){
		if(!mp[make_pair(edgex[i],edgey[i])]) link(i);
		else mp[make_pair(edgex[i],edgey[i])]=i;
	}
	for(int i=q;i>=1;--i)
		if(askopt[i]==1){
			lct.spilt(askx[i],asky[i]);
			ans[++tot]=lct.val[lct.id[askx[i]]];
		}
		else link(mp[make_pair(askx[i],asky[i])]);
	for(int i=tot;i>=1;--i) printf("%d\n",ans[i]);
	return 0;
}