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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
const int M=200010;
const int maxl=99999999;
int n,m,q,i,j,u,v,l,cnt,fa[N],up[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
struct edge{
	int f,t,l;
}w[M],W[M],w1[M];
int head[N],tail[N],next[M];
void add(int f,int t,int l){
	static int cnt=0;
	cnt++;w[cnt].f=f;w[cnt].t=t;w[cnt].l=l;
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	cnt++;w[cnt].f=t;w[cnt].t=f;w[cnt].l=l;
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
void remove(int f,int t){
	int i=head[f];
	while (w[i].t!=t) i=next[i];
	swap(w[i],w[head[f]]);
	head[f]=next[head[f]];
}
bool cmp(const edge &x,const edge &y){
	return x.l<y.l;
}
bool check[M];
int f[N][N];
struct ask{
	int k,x,y,ans;
}Q[M];
void dfs(int x){
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i].t])
		fa[w[i].t]=x,up[w[i].t]=w[i].l,dfs(w[i].t);
}
int len,lca,last,vis[N];
void LCA(int x,int y){
	static int t=1;t++;
	int a=x,b=y;
	len=-maxl;
	while (a) vis[a]=t,a=fa[a];
	while (vis[b]!=t) b=fa[b];
	lca=b;
	while (x!=lca){
		if (up[x]>len) len=up[x],last=x;
		x=fa[x];
	}
	while (y!=lca){
		if (up[y]>len) len=up[y],last=y;
		y=fa[y];
	}
}

int main()
{
	freopen("tube.in","r",stdin);
	freopen("tube.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
		f[i][j]=maxl;
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&W[i].f,&W[i].t,&W[i].l);
		f[W[i].f][W[i].t]=f[W[i].t][W[i].f]=i;
	}
	for (i=1;i<=q;i++){
		scanf("%d%d%d",&Q[i].k,&Q[i].x,&Q[i].y);
		if (Q[i].k==2) check[f[Q[i].x][Q[i].y]]=1;
	}
	cnt=0;
	for (i=1;i<=m;i++)
	if (!check[i]) w1[++cnt]=W[i];
	sort(w1+1,w1+cnt+1,cmp);
	for (i=1;i<=n;i++) fa[i]=i;
	memset(check,0,sizeof check);
	for (i=1;i<=cnt;i++){
		int a=find(w1[i].f),b=find(w1[i].t);
		if (a!=b){
			fa[b]=a;add(w1[i].f,w1[i].t,w1[i].l);
		}
	}
	memset(fa,0,sizeof fa);
	fa[1]=1;dfs(1);fa[1]=0;
	for (i=q;i>0;i--)
	if (Q[i].k==1){
		LCA(Q[i].x,Q[i].y);Q[i].ans=len;
	}
	else{
		LCA(Q[i].x,Q[i].y);
		if (len<W[f[Q[i].x][Q[i].y]].l) continue;
		remove(last,fa[last]);
		remove(fa[last],last);
		add(Q[i].x,Q[i].y,W[f[Q[i].x][Q[i].y]].l);
		memset(fa,0,sizeof fa);
		fa[1]=1;dfs(1);fa[1]=0;
	}
	for (i=1;i<=q;i++)
	if (Q[i].k==1) printf("%d\n",Q[i].ans);
	return 0;
}