记录编号	614521	评测结果	AAAAAAAAAA
题目名称	27.[WC 2006] 水管局长	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	2.223 s
提交时间	2026-04-10 11:23:54	内存使用	11.09 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct LCT{
	int fa[N],s[N][2],rev[N];
	int val[N],mx[N],pos[N];
	void up(int x){
		mx[x]=max(max(mx[s[x][0]],mx[s[x][1]]),val[x]);
		if(mx[x]==val[x])pos[x]=x;
		if(mx[x]==mx[s[x][0]])pos[x]=pos[s[x][0]];
		if(mx[x]==mx[s[x][1]])pos[x]=pos[s[x][1]];
	}
	void mktg(int x){rev[x]^=1,swap(s[x][0],s[x][1]);}
	void down(int x){
		if(!rev[x])return;
		if(s[x][0])mktg(s[x][0]);
		if(s[x][1])mktg(s[x][1]);
		rev[x]=0;return;
	}
	bool chk(int x){return s[fa[x]][1]==x;}
	bool isrt(int x){return (s[fa[x]][0]!=x&&s[fa[x]][1]!=x);}
	void rotate(int x){
		int y=fa[x],z=fa[y],c=chk(x);
		if(!isrt(y))s[z][chk(y)]=x;
		fa[x]=z,s[y][c]=s[x][c^1];
		if(s[x][c^1])fa[s[x][c^1]]=y;
		fa[y]=x,s[x][c^1]=y;
		up(y),up(x);return;
	}
	void upd(int x){
		if(!isrt(x))upd(fa[x]);
		down(x);return;
	}
	void splay(int x){
		upd(x);
		for(int f=fa[x];!isrt(x);f=fa[x]){
			if(!isrt(f))rotate(chk(f)==chk(x)?f:x);
			rotate(x);
		}
	}
	void access(int x){
		for(int p=0;x;p=x,x=fa[x]){
			splay(x),s[x][1]=p,up(x);
		}
	}
	void mkrt(int x){access(x),splay(x),mktg(x);}
	void split(int x,int y){mkrt(x),access(y),splay(y);}
	void link(int x,int y){mkrt(x);fa[x]=y;}
	void cut(int x,int y){split(x,y),fa[x]=s[y][0]=0,up(y);}
	int query(int x,int y){split(x,y);return pos[y];}
	int findrt(int x){access(x);splay(x);while(s[x][0])x=s[x][0];return x;}
	bool check(int x,int y){mkrt(x);return (findrt(y)==x);}
}tr;
int n,m,q,u[N],v[N],w[N],o[N],x[N],y[N];
map<pair<int,int>,int>H;
void add(int i){
	if(!tr.check(u[i],v[i])){
		tr.link(u[i],n+i);
		tr.link(v[i],n+i);
	}else{
		int j=tr.query(u[i],v[i])-n;
		if(w[j]>w[i]){
			tr.cut(u[j],n+j);
			tr.cut(v[j],n+j);
			tr.link(u[i],n+i);
			tr.link(v[i],n+i);
		}
	}
	return;
}
int mk[N],ans[N];
int main(){
	freopen("tube.in","r",stdin);
	freopen("tube.out","w",stdout);
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",u+i,v+i,w+i);
		if(u[i]>v[i])swap(u[i],v[i]);
		H[make_pair(u[i],v[i])]=i;
	}
	for(int i=1;i<=m;i++)tr.val[n+i]=w[i];
	for(int i=1;i<=q;i++){
		scanf("%d %d %d",o+i,x+i,y+i);
		if(x[i]>y[i])swap(x[i],y[i]);
		if(o[i]==2)mk[H[make_pair(x[i],y[i])]]=1;
	}
	for(int i=1;i<=m;i++)if(!mk[i])add(i);
	for(int i=q;i>=1;i--){
		if(o[i]==1)ans[i]=w[tr.query(x[i],y[i])-n];
		else add(H[make_pair(x[i],y[i])]);
	}
	for(int i=1;i<=q;i++){
		if(o[i]==1)printf("%d\n",ans[i]);
	}
	return 0;
}