记录编号	248973	评测结果	AAAAAAAAAA
题目名称	[WC 2006] 水管局长	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	1.202 s
提交时间	2016-04-11 18:05:23	内存使用	6.54 MiB

#include <algorithm> 
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=1010;
const int maxm=100010;
struct E{
	int u,v,w;
	bool del;
}e[maxm];
struct Ask{
	int k,a,b,d,ans;
}q[maxm];
bool cmp(E a,E b){
	if(a.u!=b.u)
		return a.u<b.u;
	return a.v<b.v;	
}
int n,m,Q;
int f[maxn],fa[maxn+maxm];
bool rt[maxn+maxm];
int Max[maxn+maxm],ch[maxn+maxm][2],flip[maxn+maxm];
int Maxp[maxn+maxm],key[maxn+maxm];
int Find(int x){
	return f[x]==x?x:f[x]=Find(f[x]);
}

void Push_up(int p){
    Max[p]=max(key[p],max(Max[ch[p][0]],Max[ch[p][1]]));
    if(Max[p]==key[p])
        Maxp[p]=p;
    else if(Max[p]==Max[ch[p][0]])
        Maxp[p]=Maxp[ch[p][0]];
    else if(Max[p]==Max[ch[p][1]])
        Maxp[p]=Maxp[ch[p][1]];
}

void Flip(int x){
	swap(ch[x][0],ch[x][1]);
	flip[x]^=1;
}

void Push_down(int x){
	if(flip[x]){
		Flip(ch[x][0]);
		Flip(ch[x][1]);
		flip[x]=0;
	}
}

void P(int x){
	if(!rt[x])P(fa[x]);
	Push_down(x);
}

void Rotate(int x){
	int y=fa[x],g=fa[y],c=ch[y][1]==x;
	ch[y][c]=ch[x][c^1];fa[ch[y][c]]=y;
	ch[x][c^1]=y;fa[y]=x;fa[x]=g;
	if(!rt[y])ch[g][ch[g][1]==y]=x;
	else rt[y]=false,rt[x]=true;
	Push_up(y);	
}

void Splay(int x){
	P(x);
	for(int y=fa[x];!rt[x];Rotate(x),y=fa[x])
		if(!rt[y])
			Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
	Push_up(x);
}

void Access(int x){
	int y=0;
	while(x){
		Splay(x);
		rt[ch[x][1]]=true;
		rt[ch[x][1]=y]=false;
		Push_up(x);
		x=fa[y=x];
	}
}

void Make_rt(int x){
	Access(x);
	Splay(x);
	Flip(x);
}

void Link(int x,int y){
	Make_rt(y);
	fa[y]=x;
}

void Cut(int x,int y){
	Make_rt(x);
	Splay(y);
	fa[ch[y][0]]=fa[y];fa[y]=0;
	rt[ch[y][0]]=true;ch[y][0]=0;
	Push_up(y);
}

void Lca(int &x,int &y){
	Access(y);y=0;
	while(true){
		Splay(x);
		if(!fa[x])break;
		rt[ch[x][1]]=true;
		rt[ch[x][1]=y]=false;
		Push_up(x);
		x=fa[y=x];
	}
}

int Query(int x,int y){
	Lca(x,y);
	if(key[x]>Max[y]&&key[x]>Max[ch[x][1]])
		return x;
	if(Max[y]<Max[ch[x][1]])
		return Maxp[ch[x][1]];
	return Maxp[y];		
}

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",&e[i].u,&e[i].v,&e[i].w);
		if(e[i].u>e[i].v)swap(e[i].u,e[i].v);e[i].del=false;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=Q;i++){
		scanf("%d%d%d",&q[i].k,&q[i].a,&q[i].b);
		if(q[i].a>q[i].b)swap(q[i].a,q[i].b);
		if(q[i].k==2){
			e[q[i].d=lower_bound(e+1,e+m+1,(E){q[i].a,q[i].b,0},cmp)-e].del=true;
		}
	}
	for(int i=1;i<=n;i++)f[i]=i,rt[i]=true;
	for(int i=1;i<=m;i++)key[i+n]=e[i].w,rt[i+n]=true;
	for(int i=1,u,v;i<=m;i++)
		if(!e[i].del){
			u=e[i].u;v=e[i].v;
			if(Find(u)!=Find(v)){
				f[Find(u)]=Find(v);
				Link(i+n,u);Link(i+n,v);
			}
			else{
				int p=Query(u,v);
				if(key[p]>e[i].w){
					Cut(p,e[p-n].u);
					Cut(p,e[p-n].v);
					Link(i+n,u);
					Link(i+n,v);
				}
			}
		}
		
	for(int i=Q;i>=1;i--){
		if(q[i].k==1)
			q[i].ans=key[Query(q[i].a,q[i].b)];
		else{
			int u=e[q[i].d].u,v=e[q[i].d].v;
			if(Find(u)!=Find(v)){
				f[Find(u)]=Find(v);
				Link(q[i].d+n,u);
				Link(q[i].d+n,v);
			}
			else{
				int p=Query(u,v);
				if(key[p]>e[q[i].d].w){
					Cut(p,e[p-n].u);
					Cut(p,e[p-n].v);
					Link(q[i].d+n,u);
					Link(q[i].d+n,v); 
				}
			}
		}
	}
	
	for(int i=1;i<=Q;i++)
		if(q[i].k==1)
			printf("%d\n",q[i].ans);
	return 0;		
}