首先吐槽一下……这题还吓唬你。都说了图中没有同色环，还说什么“所有可能从u到v的简单路径”，就一条……
很显然就是每一种颜色维护一个LCT。因为颜色很少所以多开几棵就行。
有一些要注意的：
1.在修改的时候，首先我们得先找到连接这两个点的边原来是什么颜色的。这个必须是直接相连，因为有可能这两个点在多种颜色中都是联通的（在一棵(splay)中），但是不是直接连边的。我的做法是用map维护，虽然常数大不过其实开了O2还挺快……
2.修改边的时候要维护一下点的度数，对于error2，需要判断一下是否已经联通。
3.有人说要特判更改颜色和原来一样的情况。我的写法不需要……因为我是直接模拟，先切开，不行再连上……
4.注意修改点权之后务必要(splay)一次，0分变100……
#include<bits/stdc++.h>
#define rep(i,a,n) for(register int i = a;i <= n;i++)
#define per(i,n,a) for(register int i = n;i >= a;i--)
#define I inline
using namespace std;
typedef long long ll;
const int M = 20005;
I ll read()
{
ll ans = 0,op = 1;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}
while(ch >='0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();
return ans * op;
}
int n,m,c,k,u,v,w,vi[M],op,x,y;
struct LCT
{
int ch[M][2],fa[M],rev[M],val[M],maxn[M],sta[M],top,deg[M];
map <int,bool> edge[M];
I bool get(int x) {return ch[fa[x]][1] == x;}
I bool nroot(int x) {return (ch[fa[x]][0] == x) || (ch[fa[x]][1] == x);}
I void rever(int x) {swap(ch[x][0],ch[x][1]),rev[x] ^= 1;}
I void pushup(int x) {maxn[x] = max(val[x],max(maxn[ch[x][0]],maxn[ch[x][1]]));}
I void pushdown(int x) {if(rev[x]) rever(ch[x][0]),rever(ch[x][1]),rev[x] = 0;}
I void rotate(int x)
{
int y = fa[x],z = fa[y],k = get(x);
if(nroot(y)) ch[z][get(y)] = x;
fa[x] = z,ch[y][k] = ch[x][k^1],fa[ch[x][k^1]] = y;
ch[x][k^1] = y,fa[y] = x;
pushup(y),pushup(x);
}
I void splay(int x)
{
int p = x; sta[++top] = p;
while(nroot(p)) p = fa[p],sta[++top] = p;
while(top) pushdown(sta[top--]);
while(nroot(x))
{
int y = fa[x],z = fa[y];
if(nroot(y)) ((ch[z][0] == y) ^ (ch[y][1] == x)) ? rotate(x) : rotate(y);
rotate(x);
}
}
I void access(int x) {for(int g = 0;x;g = x,x = fa[x]) splay(x),ch[x][1] = g,pushup(x);}
I void makeroot(int x) {access(x),splay(x),rever(x);}
I int findroot(int x)
{
access(x),splay(x);
while(ch[x][0]) pushdown(x),x = ch[x][0];
return x;
}
I void split(int x,int y) {makeroot(x),access(y),splay(y);}
I void link(int x,int y) {makeroot(x);if(findroot(y) != x) fa[x] = y,deg[x]++,deg[y]++,edge[x][y] = 1,edge[y][x] = 1;}
I void cut(int x,int y)
{
makeroot(x);
if(findroot(y) != x || fa[x] != y || ch[x][1]) return;
ch[y][0] = fa[x] = 0,deg[x]--,deg[y]--,edge[x][y] = 0,edge[y][x] = 0,pushup(y);
}
}T[10];
I int findcolor(int u,int v)
{
rep(i,0,c-1) if(T[i].edge[u][v] == 1) return i;
return -1;
}
int main()
{
n = read(),m = read(),c = read(),k = read();
rep(i,1,n)
{
vi[i] = read();
rep(j,0,c-1) T[j].val[i] = T[j].maxn[i] = vi[i];
}
rep(i,1,m) u = read(),v = read(),w = read(),T[w].link(u,v);
while(k--)
{
op = read();
if(op == 0) {x = read(),y = read();rep(i,0,c-1) T[i].val[x] = y,T[i].splay(x);}
else if(op == 1)
{
u = read(),v = read(),w = read();
int d = findcolor(u,v);
if(d == -1) {printf("No such edge.
");continue;}
T[d].cut(u,v);
if(T[w].deg[u] + 1 > 2 || T[w].deg[v] + 1 > 2) {printf("Error 1.
"),T[d].link(u,v);continue;}
T[w].makeroot(u);
if(T[w].findroot(v) == u) {printf("Error 2.
"),T[d].link(u,v);continue;}
T[w].link(u,v),printf("Success.
");
}
else if(op == 2)
{
w = read(),u = read(),v = read();
T[w].makeroot(u);
if(T[w].findroot(v) != u) printf("-1
");
else T[w].split(u,v),printf("%d
",T[w].maxn[v]);
}
}
return 0;
}