记录编号	333779	评测结果	AAAAAAAAAA
题目名称	[WC 2006] 水管局长	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.017 s
提交时间	2016-10-31 14:22:57	内存使用	37.50 MiB

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int N=500010;
//edge chapter
struct edge{int f,t,l,p,T;}w[N];
bool cmp(const edge &x,const edge &y){
	return x.T==y.T?x.l<y.l:x.T>y.T;
}
int n,m,q,head[N],tail[N],next[N];
void add(int i){
	w[i+m]=w[i];swap(w[i].f,w[i].t);
	int f=w[i].f,t=w[i].t;
	if (!head[f]) head[f]=tail[f]=i;
		else tail[f]=next[tail[f]]=i;
	if (!head[t]) head[t]=tail[t]=i+m;
		else tail[t]=next[tail[t]]=i+m;
}
//link cut tree chapter
int son[N][2],fa[N],v[N],mp[N],cnt,E[N];//E[x]表示边权点对应的边标号
bool root[N],rev[N];
#define lc son[x][0]
#define rc son[x][1]
void New(int i){
	v[cnt]=w[i].l;root[cnt]=1;mp[cnt]=cnt;E[cnt]=i;
	w[i].p=w[i<=m?i+m:i-m].p=cnt;
}
void update(int x){
	mp[x]=x;
	if (v[mp[lc]]>v[mp[x]]) mp[x]=mp[lc];
	if (v[mp[rc]]>v[mp[x]]) mp[x]=mp[rc]; 
}
void pushdown(int x){
	if (rev[x]){
		swap(son[lc][0],son[lc][1]);
		swap(son[rc][0],son[rc][1]);
		rev[lc]^=1;rev[rc]^=1;
		rev[0]=rev[x]=0;
	}
}
void rotate(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;else
	if (y==son[z][1]) son[z][1]=x;
	root[x]=root[y];root[y]=0;
	update(y);update(x);
}
void splay(int x){
	pushdown(x);
	while (!root[x]){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (root[y]){rotate(x);return;}
		if (x==son[y][0]) rotate(y==son[z][0]?y:x);
			else rotate(y==son[z][1]?y:x);
		rotate(x);
	}
}
void access(int x){
	splay(x);
	root[rc]=1;rc=0;
	update(x);
	while (fa[x]){
		int y=fa[x];
		splay(y);
		root[son[y][1]]=1;
		root[son[y][1]=x]=0;
		update(y);
		splay(x);
	}
}
void make_root(int x){
	access(x);
	rev[x]^=1;
	swap(lc,rc);
}
void cut(int x,int y){
	make_root(y);access(x);
	root[y]=1;lc=fa[y]=0;
	update(x);
}
void link(int x,int y,int i){
	make_root(x);
	fa[fa[x]=++cnt]=y;
	New(i);
}
//init chapter
map<pair<int,int>,int> M;
int f[N];int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void dfs(int x){
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i].t]){
		fa[fa[w[i].t]=++cnt]=x;
		New(i);dfs(w[i].t);
	}
}
struct ask{int k,x,y,ans;}Q[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",&w[i].f,&w[i].t,&w[i].l);
		w[i].T=q+1;
		M[make_pair(w[i].f,w[i].t)]=M[make_pair(w[i].t,w[i].f)]=i;
	}
	for (int i=1;i<=q;i++){
		scanf("%d%d%d",&Q[i].k,&Q[i].x,&Q[i].y);
		if (Q[i].k==2) w[M[make_pair(Q[i].x,Q[i].y)]].T=i;
	}
	//init
	sort(w+1,w+m+1,cmp);
	for (int i=1;i<=n;i++) root[i]=1,mp[i]=f[i]=i;
	for (int i=1;i<=m;i++)
	if (w[i].T==q+1){
		int a=find(w[i].f),b=find(w[i].t);
		if (a!=b){f[a]=b;add(i);}
	}
	cnt=n;fa[1]=1;dfs(1);fa[1]=0;
	//solve
	int pos=1;while (w[pos].T==q+1) pos++;
	for (int i=q;i;i--){
		int x=Q[i].x,y=Q[i].y;
		make_root(x);
		access(y);
		if (Q[i].k==1) Q[i].ans=v[mp[y]];
		else{
			if (v[mp[y]]>=w[pos].l){
				int e=E[mp[y]];
				cut(w[e].f,w[e].p);
				cut(w[e].t,w[e].p);
				link(x,y,pos);
			}
			pos++;
		}
	}
	for (int i=1;i<=q;i++)
	if (Q[i].k==1) printf("%d\n",Q[i].ans);
	return 0;
}