[ZJOI2012]网络
思路
显然，这是一道lct裸题。因为颜色不多，所以对于每一种颜色的边我们都建一个lct即可。(我这里是用 （颜色×n+点的标号） 表示每一种颜色lct)
操作0
因为我们对于每一种颜色的边都建了一个lct所以，我们对于每一种颜色的边都update一次。(虽然很暴力，但跑得过)
操作1
1.其实对于判断边不存在的情况，我们可以用临接矩阵来存，开一个bool数组10000*10000 128M还是开得下的。这样节约了很多时间(其实是我懒得想其它方法判断)。
2.错误1,开一个degree记录每个点每一种颜色的边的度即可。
3.错误2,判断一下两点在这个颜色的lct是否联通，若联通即为不合法的情况，至于怎么判断，lct模板。
4.对于可以修改颜色的情况，我们就把原来颜色的边cut掉，再link新的颜色就可以了。看下面大佬都是用临接表存边找颜色，我这里教你们一招(懒人专用的奇淫技巧)把bool数组开成char数组这样既可以判断边的存在性，又可以判断边的颜色，比那些临接表方便了许多，还节约了时间。(其实对于一些空间不够的题，可以用short或者char之类的数组来存东西，也许这样就够了)
操作2
没有什么特殊的地方和其它lct题的查询没有什么区别。
总结
这题lct的部分跟其它题目没有区别，直接复制粘贴都可以，只是要想到能开多个lct并且这些lct之间互不影响，实现起来还是非常简单的
代码
#includeusing namespace std;const int N=2e5;int fa[N],ch[N][2],lazy[N],w[N],ans[N],degree[N],n,m,c;char pd[10001][10001];int isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}int get(int x){return ch[fa[x]][1]==x;}void pushup(int x){ans[x]=max(w[x],max(ans[ch[x][0]],ans[ch[x][1]]));}void pushdown(int x){ if(!lazy[x])return; swap(ch[x][0],ch[x][1]); lazy[ch[x][0]]^=1; lazy[ch[x][1]]^=1; lazy[x]^=1;}void rotate(int x){ int y=fa[x],z=fa[y],k=get(x); fa[x]=z;if(!isroot(y))ch[z][ch[z][1]==y]=x; ch[y][k]=ch[x][k^1];fa[ch[y][k]]=y; ch[x][k^1]=y;fa[y]=x; pushup(y);pushup(x);}void push(int x){if(!isroot(x))push(fa[x]);pushdown(x);}void splay(int x){ push(x); while(!isroot(x)){ int y=fa[x]; if(!isroot(y)) if(get(x)==get(y))rotate(y); else rotate(x); rotate(x); }}void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,pushup(x);}void makeroot(int x){access(x);splay(x);lazy[x]^=1;}void split(int x,int y){makeroot(x);access(y);splay(y);}void link(int x,int y){makeroot(x);fa[x]=y;}void cut(int x,int y){split(x,y);fa[x]=ch[y][0]=0;pushup(y);}int getroot(int x){ access(x);splay(x); while(ch[x][0])x=ch[x][0]; return x;}int query(int x,int y){ if(getroot(x)!=getroot(y))return -1; split(x,y); return ans[y];}void update(int x,int y){ makeroot(x); w[x]=y; pushup(x);}void work(int x,int y,int z){ if(pd[x][y]==0){printf("No such edge.\n");return;} int u=x+z*n,v=y+z*n,lu=x+pd[x][y]*n,lv=y+pd[x][y]*n; if(pd[x][y]==z){printf("Success.\n");return;} if(degree[u]==2||degree[v]==2){printf("Error 1.\n");return;} if(getroot(u)==getroot(v)){printf("Error 2.\n");return;} degree[lu]--;degree[lv]--; degree[u]++;degree[v]++; cut(lu,lv); link(u,v); printf("Success.\n"); pd[x][y]=z; pd[y][x]=z;}int main(){ int k; cin>>n>>m>>c>>k; for(int i=1;i<=n;++i){ scanf("%d",&w[i]);ans[i]=w[i]; for(int j=1;j<=c;++j) ans[i+j*n]=w[i+j*n]=w[i]; } for(int i=1;i<=m;++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); w++; int x=u+w*n,y=v+w*n; link(x,y); degree[x]++; degree[y]++; pd[u][v]=w; pd[v][u]=w; } while(k--){ int op; scanf("%d",&op); if(op==0){ int x,y; scanf("%d%d",&x,&y); for(int i=1;i<=c;++i) update(x+i*n,y); } if(op==1){ int x,y,z; scanf("%d%d%d",&x,&y,&z);z++; work(x,y,z); } if(op==2){ int x,y,z; scanf("%d%d%d",&z,&x,&y);z++; printf("%d\n",query(x+z*n,y+z*n)); } } return 0;}