题解：
很显然会发现对于每种颜色分开处理这是一颗树
然后就是裸的lct
有个坑就是判断操作1 可能颜色改成跟原先一样的
代码：
#include <bits/stdc++.h>
using namespace std;
#define N 11000
#define M 15
int n,m,c,kk;
int cnt[M][N],v[N];
struct lct{
int data[N],fa[N];
int leftson[N],rightson[N];
int count2[N];
bool rev[N];
void down(int x)
{
if (!rev[x]) return;
swap(leftson[x],rightson[x]); rev[x]=0;
rev[leftson[x]]^=1; rev[rightson[x]]^=1;
}
void updata(int x)
{
down(x);
count2[x]=count2[leftson[x]]+count2[rightson[x]]+1;
data[x]=max(v[x],max(data[leftson[x]],data[rightson[x]]));
}
bool pd(int x)
{
int y=fa[x];
if (leftson[y]!=x&&rightson[y]!=x) return false;
else return (true);
}
void rotate(int x,int y)
{
int father=fa[x];
if (y==1)
{
rightson[father]=leftson[x];
if (leftson[x]) fa[leftson[x]]=father;
} else
{
leftson[father]=rightson[x];
if (rightson[x]) fa[rightson[x]]=father;
}
fa[x]=fa[father];
if (pd(father))
{
if (leftson[fa[x]]==father)
leftson[fa[x]]=x;
else rightson[fa[x]]=x;
}
fa[father]=x;
if (y==1) leftson[x]=father;
else rightson[x]=father;
updata(father); updata(x);
}
void dfs(int x)
{
if (pd(x)) dfs(fa[x]);
down(x);
}
void splay(int x)
{
dfs(x);
int father=fa[x];
while (pd(x))
{
if (!pd(father))
{
if (x==leftson[father]) rotate(x,2);
else rotate(x,1);
} else
{
if (father==leftson[fa[father]])
if (x==leftson[father])
rotate(father,2),rotate(x,2);
else rotate(x,1),rotate(x,2);
else
if (x==rightson[father])
rotate(father,1),rotate(x,1);
else rotate(x,2),rotate(x,1);
}
father=fa[x];
}
}
void access(int x)
{
for (int y=0;x;y=x,x=fa[x])
splay(x),rightson[x]=y,updata(x);
}
void makeroot(int x)
{
access(x);
splay(x);
rev[x]^=1;
}
int findroot(int x)
{
access(x);
splay(x);
while (leftson[x]) x=leftson[x];
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
bool link(int x,int y)
{
makeroot(x);
if (findroot(y)!=x)
{
fa[x]=y;
return(1);
}
else return(0);
}
void cut(int x,int y)
{
makeroot(x);
if (findroot(y)==x&&fa[x]==y)
{
fa[x]=leftson[y]=0;
updata(y);
}
}
} num[M];
struct hash{
#define mo 5000007
int cc=11000;
struct {
int a,b,c;
}f[mo+1000];
void push(int x,int y,int z)
{
int tmp=(cc*x+y)%mo;
while (f[tmp].a) tmp=tmp%mo+1;
f[tmp].a=x; f[tmp].b=y; f[tmp].c=z;
}
int find(int x,int y)
{
int tmp=(cc*x+y)%mo;
while (f[tmp].a&&(!(f[tmp].a==x&&f[tmp].b==y))) tmp=tmp%mo+1;
if (f[tmp].a==x&&f[tmp].b==y) return(tmp);
else return(-1);
}
}hash;
int main()
{
freopen("network.in","r",stdin);
freopen("network.out","w",stdout);
cin>>n>>m>>c>>kk;
for (int i=1;i<=n;i++)
cin>>v[i];
for (int i=1;i<=m;i++)
{
int c,d,e;
cin>>c>>d>>e;
hash.push(c,d,e); hash.push(d,c,e);
cnt[e][c]++; cnt[e][d]++;
num[e].link(c,d);
}
int k,x,y,z;
for (int i=1;i<=kk;i++)
{
cin>>k;
if (k==0)
{
cin>>x>>y;
for (int i=0;i<c;i++)
{
num[i].access(x);
num[i].splay(x);
v[x]=y;
num[i].updata(x);
}
}
if (k==1)
{
cin>>x>>y>>z;
int tmp=hash.find(x,y),tmp2=hash.find(y,x),tmp3=hash.f[tmp].c;
if (tmp==-1) cout<<"No such edge."<<endl; else
if (tmp3==z) cout<<"Success."<<endl; else
if ((cnt[z][x]==2||cnt[z][y]==2)) cout<<"Error 1."<<endl; else
if (num[z].link(x,y))
{
num[tmp3].cut(x,y);
hash.f[tmp].c=z; hash.f[tmp2].c=z;
cnt[tmp3][x]--; cnt[tmp3][y]--;
cnt[z][x]++; cnt[z][y]++;
cout<<"Success."<<endl;
} else cout<<"Error 2."<<endl;
}
if (k==2)
{
cin>>z>>x>>y;
num[z].makeroot(x);
if (num[z].findroot(y)==x)
{
num[z].split(x,y);
cout<<num[z].data[y]<<endl;;
} else cout<<-1<<endl;
}
}
return 0;
}