记录编号	143837	评测结果	AAAAAAAAAA
题目名称	[WC 2006] 水管局长	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.377 s
提交时间	2014-12-18 08:44:09	内存使用	43.23 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
int getint(){
    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;
}
const int SIZEN=100010,SIZEM=1000010,SIZEQ=100010;
inline int min(int a,int b,int c){return min(a,min(b,c));}
int Weight[SIZEM];
class Node{
public:
	int lc,rc,fa;
	int val,mx;
	bool rev;
	void clear(int t){
		lc=rc=fa=0;
		val=mx=t;
		rev=0;
	}
	Node(){clear(0);}
	#define lc(x) Tree[x].lc
	#define rc(x) Tree[x].rc
	#define fa(x) Tree[x].fa
	#define val(x) Tree[x].val
	#define mx(x) Tree[x].mx
	#define rev(x) Tree[x].rev
};
Node Tree[SIZEN+SIZEM];
bool Is_Root(int x){
	return lc(fa(x))!=x&&rc(fa(x))!=x;
}
void Push_Down(int x){
	if(!x) return;
	if(rev(x)){
		swap(lc(x),rc(x));
		rev(lc(x))^=1;rev(rc(x))^=1;
		rev(x)=0;
	}
}
void Update(int x){
	if(!x) return;
	mx(x)=val(x);
	if(Weight[mx(lc(x))]>Weight[mx(x)]) mx(x)=mx(lc(x));
	if(Weight[mx(rc(x))]>Weight[mx(x)]) mx(x)=mx(rc(x));
}
void Zig(int x){//右旋
	int y=fa(x),z=fa(y);
	if(lc(z)==y) lc(z)=x;
	if(rc(z)==y) rc(z)=x;
	fa(x)=z;
	lc(y)=rc(x);fa(lc(y))=y;
	rc(x)=y;fa(y)=x;
	Update(y);Update(x);
}
void Zag(int x){//左旋
	int y=fa(x),z=fa(y);
	if(lc(z)==y) lc(z)=x;
	if(rc(z)==y) rc(z)=x;
	fa(x)=z;
	rc(y)=lc(x);fa(rc(y))=y;
	lc(x)=y;fa(y)=x;
	Update(y);Update(x);
}
void Splay(int x){
	Push_Down(x);
	while(!Is_Root(x)){
		int y=fa(x),z=fa(y);
		Push_Down(z);Push_Down(y);Push_Down(x);
		if(Is_Root(y)){
			if(lc(y)==x) Zig(x);
			else Zag(x);
			return;
		}
		if(lc(z)==y){
			if(lc(y)==x) Zig(y),Zig(x);
			else Zag(x),Zig(x);
		}
		else{
			if(rc(y)==x) Zag(y),Zag(x);
			else Zig(x),Zag(x);
		}
	}
}
void Access(int x){
	int y=0;
	while(x){
		Splay(x);
		rc(x)=y;
		Update(x);
		y=x;
		x=fa(x);
	}
}
int Get_Root(int x){
	Access(x);
	Splay(x);
	while(lc(x)){
		Push_Down(x);
		x=lc(x);
	}
	return x;
}
void Make_Root(int x){
	Access(x);
	Splay(x);
	rev(x)^=1;
}
void Link(int x,int y){
	Make_Root(y);
	fa(y)=x;
	Splay(y);
}
void Cut(int x,int y){
	Make_Root(x);
	Access(y);
	Splay(y);
	fa(lc(y))=0;lc(y)=0;
	Update(y);
}
int Path_Query(int x,int y){
	Make_Root(x);
	Access(y);
	Splay(y);
	return mx(y);
}
class Edge{
public:
	int u,v,w;
};
bool operator < (Edge a,Edge b){
	return a.w<b.w;
}
Edge E[SIZEM];
class Request{
public:
	int cmd;
	int u,v;
};
Request R[SIZEQ];
map<pair<int,int>,int> lis;
bool broken[SIZEM];
int N,M,Q;
void Cut_Edge(int k){
	Cut(E[k].u,N+k);
	Cut(E[k].v,N+k);
}
void Link_Edge(int k){
	Weight[k]=E[k].w;
	Tree[N+k].clear(k);
	Link(E[k].u,N+k);
	Link(E[k].v,N+k);
}
void Add_Edge(int k){//尝试加入k号边
	int g1=Get_Root(E[k].u),g2=Get_Root(E[k].v);
	if(g1!=g2) Link_Edge(k);
	else{
		int e=Path_Query(E[k].u,E[k].v);
		if(Weight[e]>E[k].w){
			Cut_Edge(e);
			Link_Edge(k);
		}
	}
}
void Make_Tree(void){
	for(int i=1;i<=M;i++)
		if(!broken[i]) Add_Edge(i);
}
void Process(void){
	static int ans[SIZEQ];
	for(int i=Q;i>=1;i--){
		if(R[i].cmd==1){
			int k=Path_Query(R[i].u,R[i].v);
			ans[i]=Weight[k];
		}
		else{
			int k=lis[make_pair(R[i].u,R[i].v)];
			Add_Edge(k);
		}
	}
	for(int i=1;i<=Q;i++)
		if(R[i].cmd==1) printf("%d\n",ans[i]);
}
void Init(void){
	N=getint();M=getint();Q=getint();
	for(int i=1;i<=M;i++){
		E[i].u=getint();E[i].v=getint();E[i].w=getint();
		if(E[i].u>E[i].v) swap(E[i].u,E[i].v);
		lis[make_pair(E[i].u,E[i].v)]=i;
	}
	for(int i=1;i<=Q;i++){
		R[i].cmd=getint();R[i].u=getint();R[i].v=getint();
		if(R[i].u>R[i].v) swap(R[i].u,R[i].v);
		if(R[i].cmd==2) broken[lis[make_pair(R[i].u,R[i].v)]]=true;
	}
}
int main(){
	freopen("tube.in","r",stdin);
	freopen("tube.out","w",stdout);
	Init();
	Make_Tree();
	Process();
	return 0;
}