传送门
直接对于每种颜色都建一棵LCT就行了，至于判断能否修改，有一个特殊情况就是修改前和修改后的颜色可能相同
还有就是修改点权记得update
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e4+10,N=1e4;
map<int,int>mp;
struct LCT{
int st[maxn],v[maxn],tag[maxn],mx[maxn],ch[maxn][2],f[maxn];
int isroot(int x){return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;}
void update(int x){mx[x]=max(mx[ch[x][0]],max(mx[ch[x][1]],v[x]));}
void reverse(int x){tag[x]^=1,swap(ch[x][0],ch[x][1]);}
void pushdown(int x){
if(tag[x]){
if(ch[x][0])reverse(ch[x][0]);
if(ch[x][1])reverse(ch[x][1]);
tag[x]^=1;
}
}
void move(int x){
int fa=f[x],faa=f[fa],tmp=ch[fa][1]==x;
if(!isroot(fa))ch[faa][ch[faa][1]==fa]=x;
ch[fa][tmp]=ch[x][tmp^1],f[ch[x][tmp^1]]=fa;
ch[x][tmp^1]=fa,f[fa]=x,f[x]=faa;
update(fa),update(x);
}
void splay(int x){
int z=0,y=x;st[++z]=y;
while(!isroot(y))st[++z]=y=f[y];
while(z)pushdown(st[z]),z--;
while(!isroot(x)){
y=f[x],z=f[y];
if(!isroot(y)){
if((ch[y][0]==x)^(ch[z][0]==y))move(y);
else move(x);
}
move(x);
}
update(x);
}
void access(int x){
int y=0;
while(x){
splay(x),ch[x][1]=y;
update(x),y=x,x=f[x];
}
}
int findroot(int x){
access(x),splay(x);int now=x;
while(ch[now][0])pushdown(now),now=ch[now][0];
return pushdown(now),splay(now),now;
}
void makeroot(int x){access(x),splay(x),reverse(x);}
void split(int x,int y){makeroot(x),access(y),splay(y);}
void link(int x,int y){makeroot(x),f[x]=y;}
void cut(int x,int y){split(x,y),ch[y][0]=f[x]=0,update(y);}
}c[15];
int n,m,col,k,val[maxn],tot[maxn][15];
int main(){
read(n),read(m),read(col),read(k);
for(rg int i=1;i<=n;i++){
read(val[i]);
for(rg int j=1;j<=col;j++)c[j].v[i]=val[i];
}
for(rg int i=1,x,y,z;i<=m;i++){
read(x),read(y),read(z),z++;
c[z].link(x,y);mp[x*N+y]=mp[y*N+x]=z;
tot[x][z]++,tot[y][z]++;
}
for(rg int i=1,op,x,y,z;i<=k;i++){
read(op);
if(op==0){
read(x),read(y);
for(rg int j=1;j<=col;j++)c[j].access(x),c[j].v[x]=y,c[j].splay(x);
}
if(op==1){
read(x),read(y),read(z);int now=mp[x*N+y];z++;
if(!now){printf("No such edge.
");continue;}
tot[x][z]++,tot[y][z]++,tot[x][now]--,tot[y][now]--;
if(tot[x][z]>2||tot[y][z]>2){
tot[x][z]--,tot[y][z]--,tot[x][now]++,tot[y][now]++;
printf("Error 1.
");continue;
}
if(c[z].findroot(x)==c[z].findroot(y)&&now!=z){
tot[x][z]--,tot[y][z]--,tot[x][now]++,tot[y][now]++;
printf("Error 2.
");continue;
}
c[now].cut(x,y),c[z].link(x,y),mp[x*N+y]=mp[y*N+x]=z;
printf("Success.
");
}
if(op==2){
read(z),read(x),read(y),z++;
if(c[z].findroot(x)!=c[z].findroot(y)){printf("-1
");continue;}
c[z].split(x,y),printf("%d
",c[z].mx[y]);
}
}
}