记录编号	403668	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2012] 网络	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.501 s
提交时间	2017-05-11 08:21:57	内存使用	7.63 MiB

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int N=2e4+10,E=2e5+10;
int n,m,c,k,val[N];
int color[E];
map<pair<int,int>,int> M;
struct LCT{
	int w[N],head[N],next[N],edge[N],cnt;
	void add(int f,int t){
		w[++cnt]=t;
		next[cnt]=head[f];
		head[f]=cnt;
		edge[f]++;
	}
	int fa[N],son[N][2],Max[N];
	bool rev[N],root[N];
	#define lc son[x][0]
	#define rc son[x][1]
	void dfs(int x,int Fa){
		root[x]=1;Max[x]=val[x];
		for (int i=head[x];i;i=next[i])
		if (w[i]!=Fa) fa[w[i]]=x,dfs(w[i],x);
	}
	void init(){
		for (int i=1;i<=n;i++)
		if (!root[i]) dfs(i,0);
	}
	void update(int x){
		Max[x]=val[x];
		if (lc) Max[x]=max(Max[x],Max[lc]);
		if (rc) Max[x]=max(Max[x],Max[rc]); 
	}
	void flip(int x){
		swap(lc,rc);rev[x]^=1;
	}
	void pushdown(int x){
		if (rev[x]){
			if (lc) flip(lc);
			if (rc) flip(rc);
			rev[x]=0;
		}
	}
	void rot(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);
		for (;!root[x];rot(x)){
			int y=fa[x],z=fa[y];
			pushdown(z);pushdown(y);pushdown(x);
			if (!root[y]) rot((x==son[y][0])==(y==son[z][0])?y: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 makeroot(int x){
		access(x);flip(x);
	}
	bool islink(int x,int y){
		makeroot(x);
		int z=y;
		while (fa[z]) z=fa[z];
		access(y);
		return z==x;
	}
	void link(int x,int y){
		fa[x]=y;edge[x]++;edge[y]++;
	}
	void cut(int x,int y){
		makeroot(y);
		access(x);
		root[lc]=1;fa[lc]=0;lc=0;
		update(x);
		edge[x]--;edge[y]--;
	}
}lct[10];
int main()
{
	freopen("networkzj.in","r",stdin);
	freopen("networkzj.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&c,&k);
	for (int i=1;i<=n;i++) scanf("%d",&val[i]);
	for (int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d%d",&u,&v,&color[i]);
		M[make_pair(u,v)]=M[make_pair(v,u)]=i;
		lct[color[i]].add(u,v);
		lct[color[i]].add(v,u);
	}
	for (int i=0;i<c;i++) lct[i].init();
	while (k--){
		int tp,u,v,w;
		scanf("%d%d%d",&tp,&u,&v);
		if (!tp){
			for (int i=0;i<c;i++) lct[i].access(u);
			val[u]=v;
			for (int i=0;i<c;i++) lct[i].update(u);
		}
		else scanf("%d",&w);
		if (tp==1){
			int id=M[make_pair(u,v)];
			if (!id){
				puts("No such edge.");
				continue;
			}
			if (w==color[id]){
				puts("Success.");
				continue;
			}
			if (lct[w].edge[u]>1||lct[w].edge[v]>1){
				puts("Error 1.");
				continue;
			}
			if (lct[w].islink(u,v)){
				puts("Error 2.");
				continue;
			}
			lct[color[id]].cut(u,v);
			lct[color[id]=w].link(u,v);
			puts("Success.");
		}
		if (tp==2){
			if (!lct[u].islink(v,w)) puts("-1");
			else printf("%d\n",lct[u].Max[w]);
		}
	}
	return 0;
}