看完我之前那篇如果觉得在函数内打亿遍 int id 太麻烦了可以参考这份代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]
#define fa(p) tr[p].f
struct node{int ch[2],f,s,v,tag;};
struct LCT
{
	node tr[N];
	bool notrt(int p){return lc(fa(p))==p||rc(fa(p))==p;}
	void pushup(int p){tr[p].s=max({lc(p)?tr[lc(p)].s:0,tr[p].v,rc(p)?tr[rc(p)].s:0});}
	void pushdown(int p)
	{
		if(tr[p].tag)
		{
			swap(lc(p),rc(p));
			tr[lc(p)].tag^=1,tr[rc(p)].tag^=1;
			tr[p].tag=0;
		}
	}
	void pushall(int p)
	{
		if(notrt(p))pushall(fa(p));
		pushdown(p);
	}
	void rotate(int x)
	{
		int y=fa(x),z=fa(y),k=rc(y)==x;
		if(notrt(y))tr[z].ch[rc(z)==y]=x;fa(x)=z;
		tr[y].ch[k]=tr[x].ch[k^1];fa(tr[y].ch[k])=y;
		tr[x].ch[k^1]=y;fa(y)=x;
		pushup(y);pushup(x);
	}
	void splay(int x)
	{
		pushall(x);
		while(notrt(x))
		{
			int y=fa(x),z=fa(y);
			if(notrt(y))((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
			rotate(x);
		}
	}
	void access(int x)
	{
		for(int y=0;x;)
		{
			splay(x);
			rc(x)=y;
			pushup(x);
			y=x;x=fa(x);
		}
	}
	void makert(int x)
	{
		access(x);
		splay(x);
			tr[x].tag^=1;
	}
	void split(int x,int y)
	{
		makert(x);
		access(y);
		splay(y);
	}
	int findrt(int x)
	{
		access(x);
		splay(x);
		while(lc(x))pushdown(x),x=lc(x);
		splay(x);
		return x;
	}
	void link(int x,int y)
	{
		makert(x);
		if(findrt(y)!=x)
			fa(x)=y;
	}
	bool cut(int x,int y)
	{
		makert(x);
		if(findrt(y)==x&&fa(y)==x&&!lc(y))	
		{
			fa(y)=0,pushup(x);
			return 1;
		}
		return 0;
	}
	void change(int x,int y)
	{
		splay(x);
		tr[x].v=y;
		pushup(x);
	}
}tr[15];
int a[N],rd[15][N];map<pair<int,int>,int>mp;
int main()
{
	int n,m,C,q;cin>>n>>m>>C>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		for(int j=1;j<=C;j++)tr[j].change(i,a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,c;cin>>x>>y>>c;c++;
		tr[c].link(x,y);rd[c][x]++;rd[c][y]++;
		mp[{x,y}]=mp[{y,x}]=c;
	}
	while(q--)
	{
		int op;cin>>op;
		if(op==0)
		{
			int x,y;cin>>x>>y;
			for(int i=1;i<=C;i++)tr[i].change(x,y);
		}
		if(op==1)
		{
			int x,y,c;cin>>x>>y>>c;c++;
			if(!mp[{x,y}])
			{
				cout<<"No such edge."<<'\n';
				continue;
			}
			if((rd[c][x]==2||rd[c][y]==2)&&mp[{x,y}]!=c)
			{
				cout<<"Error 1."<<'\n';
				continue;
			}
			if(tr[c].findrt(x)==tr[c].findrt(y)&&mp[{x,y}]!=c)
			{
				cout<<"Error 2."<<"\n";
				continue;
			}
			int lstc=mp[{x,y}];
			rd[lstc][x]--;rd[lstc][y]--;
			tr[lstc].cut(x,y);
			rd[c][x]++;rd[c][y]++;
			tr[c].link(x,y);mp[{x,y}]=mp[{y,x}]=c;
			cout<<"Success."<<'\n';
		}
		if(op==2)
		{
			int c,x,y;cin>>c>>x>>y;c++;
			if(tr[c].findrt(y)!=tr[c].findrt(x)){cout<<-1<<'\n';continue;}
			tr[c].split(x,y);
			cout<<tr[c].tr[y].s<<'\n';
		}
	}
	return 0;
}

手搓的第三道紫。

十个颜色啥意思？那就开十棵动态树。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
#define lc(p) tr[id][p].ch[0]
#define rc(p) tr[id][p].ch[1]
#define fa(p) tr[id][p].f
struct node{int ch[2],f,s,tag;}tr[11][N];int v[N],rd[11][N];
map<pair<int,int>,int>mp;
bool notrt(int id,int p){return (lc(fa(p))==p)||(rc(fa(p))==p);}
void pushup(int id,int p){tr[id][p].s=max({tr[id][lc(p)].s,v[p],tr[id][rc(p)].s});}
void pushdown(int id,int p)
{
	if(tr[id][p].tag)
	{
		swap(lc(p),rc(p));
		tr[id][lc(p)].tag^=1;tr[id][rc(p)].tag^=1;
		tr[id][p].tag=0;
	}
}
void pushall(int id,int x)
{
	if(notrt(id,x))pushall(id,fa(x));
	pushdown(id,x);
}
void rotate(int id,int x)
{
	int y=fa(x),z=fa(y),k=rc(y)==x;
	if(notrt(id,y))tr[id][z].ch[rc(z)==y]=x;fa(x)=z;
	tr[id][y].ch[k]=tr[id][x].ch[k^1];fa(tr[id][x].ch[k^1])=y;
	tr[id][x].ch[k^1]=y;fa(y)=x;
	pushup(id,y);pushup(id,x);
}
void splay(int id,int x)
{
	pushall(id,x);
	while(notrt(id,x))
	{
		int y=fa(x),z=fa(y);
		if(notrt(id,y))((rc(y)==x)^(rc(z)==y))?rotate(id,x):rotate(id,y);
		rotate(id,x);
	}
}
void access(int id,int x)
{
	for(int y=0;x;)
	{
		splay(id,x);
		rc(x)=y;
		pushup(id,x);
		y=x;x=fa(x);
	}
}
void makert(int id,int x)
{
	access(id,x);
	splay(id,x);
	tr[id][x].tag^=1;
}
void split(int id,int x,int y)
{
	makert(id,x);
	access(id,y);
	splay(id,y);
}
int findrt(int id,int x)
{
	access(id,x);
	splay(id,x);
	while(lc(x))pushdown(id,x),x=lc(x);
	splay(id,x);
	return x;
}
void link(int id,int x,int y)
{
	makert(id,x);
	if(findrt(id,y)!=x)
		fa(x)=y;
}
void cut(int id,int x,int y)
{
	makert(id,x);
	if(findrt(id,y)==x&&fa(y)==x&&!lc(y))
		fa(y)=0,pushup(id,x);
}
int main()
{
	int n,m,c,k;cin>>n>>m>>c>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i];
		for(int j=1;j<=c;j++)tr[j][i].s=v[i];
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,w;cin>>x>>y>>w;w++;
		mp[{x,y}]=mp[{y,x}]=w;
		link(w,x,y);
		rd[w][x]++,rd[w][y]++;
	}
	while(k--)
	{
		int op,x,y,k;cin>>op;
		if(op==0)
		{
			cin>>x>>y;
			for(int i=1;i<=c;i++)makert(i,x);
			v[x]=y;
			for(int i=1;i<=c;i++)pushup(i,x);
		}
		if(op==1)
		{
			cin>>x>>y>>k;k++;
			if(!mp[{x,y}])
			{
				cout<<"No such edge."<<'\n';
				continue;
			}
			if(rd[k][x]>=2||rd[k][y]>=2)
			{
				if(mp[{x,y}]==k)cout<<"Success."<<'\n';
				else cout<<"Error 1."<<'\n';
				continue;
			}
			makert(k,x);
			if(findrt(k,y)==x)
			{
				if(mp[{x,y}]==k)cout<<"Success."<<'\n';
				else cout<<"Error 2."<<'\n';
				continue;
			}
			cut(mp[{x,y}],x,y);rd[mp[{x,y}]][x]--,rd[mp[{x,y}]][y]--;
			link(k,x,y);mp[{x,y}]=mp[{y,x}]=k;rd[k][x]++;rd[k][y]++;			
			cout<<"Success."<<'\n';
		}
		if(op==2)
		{
			cin>>k>>x>>y;k++;
			makert(k,x);
			if(findrt(k,y)!=x)
			{
				cout<<-1<<'\n';
				continue;
			}
			split(k,x,y);
			cout<<tr[k][y].s<<'\n';
		}
	}
	return 0;
}