链接

　　https://www.luogu.org/problem/show?pid=2173

题解

　　哎呀 折磨人的题啊

　　LCT全套操作，超级大模板。

　　首先把整个图分成C层，改一条边的颜色就相当于在一个图中把这条边去掉，在另一张图中加上这个边。

　　把LCT的操作在这里铺一下吧：

　　access: 访问这个点(略)

　　makeroot(x): 将这个点设为根，那就access(x),splay(x),tag(x)      其中tag(x)表示给这个点打上rev标记

　　link(x,y): makeroot(x),x->f=y;        其中tag(x)表示给这个点打上rev标记；就是先访问、然后转到根

　　cut(x,y): makeroot(x),splay(y),x->f=y->ch[0]=0;      如果x->ch[1]存在，则说明边（x,y）不存在

　　findroot(x): 顺着x->f往上找直到走不动为止，这个用来判断两个点是否在同一棵树上

　　对链(x,y)的操作：makeroot(x),access(y)，这样x所在的平衡树就是这条链，然后想干什么就可以干什么啦 

　　PS：这道题要求不能让链变成树，可以直接用度来控制。

代码

//LCT #include <cstdio> #include <algorithm> #define maxn 500000 using namespace std; struct node { int w, max, rev; node *ch[2], *f; }nd[maxn], *s[maxn]; int N, M, C, Q, du[maxn]; inline int getwh(node *x) {if(x->f==0)return -1;if(x->f->ch[0]==x)return 0;if(x->f->ch[1]==x)return 1;return -1;} inline bool isroot(node *x){return getwh(x)==-1;} inline void join(node *x, node *y, int wh){if(x)x->f=y;if(y)y->ch[wh]=x;} inline void tag(node *x){if(x)x->rev^=1;} inline void pushdown(node *x) { if(x->rev) { swap(x->ch[0],x->ch[1]); tag(x->ch[0]),tag(x->ch[1]); x->rev=0; } } void pushup(node *x) { int &t=x->max=x->w; if(x->ch[0])t=max(t,x->ch[0]->max); if(x->ch[1])t=max(t,x->ch[1]->max); } inline void rotate(node *x) { node *y=x->f, *z=y->f; int c=getwh(x); if(!isroot(y))join(x,z,getwh(y)); else x->f=y->f; join(x->ch[!c],y,c); join(y,x,!c); pushup(y),pushup(x); } inline void splay(node *x) { int top=0; node *y; for(y=x;!isroot(y);y=y->f)s[++top]=y;s[++top]=y; for(;top;top--)pushdown(s[top]); while(!isroot(x)) { y=x->f; if(isroot(y)){rotate(x);break;} if(getwh(x)^getwh(y))rotate(x); else rotate(y); rotate(x); } } inline void access(node *x) { node *t=0; while(x) { splay(x); x->ch[1]=t; pushup(x); t=x;x=x->f; } } inline void makeroot(node *x){access(x);splay(x);tag(x);} inline void link(node *x, node *y) {makeroot(x);x->f=y;du[x-nd]++,du[y-nd]++;} inline bool cut(node *x, node *y) { makeroot(x);access(y);splay(y); if(x->f==y and x->ch[1]==0){x->f=y->ch[0]=0;du[x-nd]--,du[y-nd]--;return true;} return false; } inline node* findroot(node *x) { while(x->f)x=x->f; return x; } inline int table(int x, int c){return c*N+x;} int main() { int type, i, x, y, z, u, v, w; node *a, *b; scanf("%d%d%d%d",&N,&M,&C,&Q); for(i=1;i<=N;i++) { scanf("%d",&x); for(int j=0;j<C;j++)nd[table(i,j)].w=nd[table(i,j)].max=x; } for(i=1;i<=M;i++) { scanf("%d%d%d",&u,&v,&w); link(nd+table(u,w),nd+table(v,w)); } while(Q--) { scanf("%d%d%d",&type,&x,&y); if(type==0) { for(i=0;i<C;i++) { splay(nd+table(x,i)); nd[table(x,i)].w=y; pushup(nd+table(x,i)); } } if(type==1) { scanf("%d",&w); for(i=0;i<C;i++)if(cut(nd+table(x,i),nd+table(y,i)))break; if(i==C){printf("No such edge.\n");continue;} a=nd+table(x,w),b=nd+table(y,w); if(du[a-nd]==2 or du[b-nd]==2) { printf("Error 1.\n"); link(nd+table(x,i),nd+table(y,i)); continue; } if(findroot(a)==findroot(b)) { printf("Error 2.\n"); link(nd+table(x,i),nd+table(y,i)); continue; } link(a,b); printf("Success.\n"); } if(type==2) { scanf("%d",&z); a=nd+table(y,x), b=nd+table(z,x); if(findroot(a)!=findroot(b)){printf("-1\n");continue;} makeroot(a);access(b);splay(b); printf("%d\n",b->max); } } return 0; }