由于珂朵莉树的题解代码都不是很适合理解，贴上我的代码

注意询问时如果你是记录了上一次颜色段的结尾颜色，要按dfn倒序算，因为链尾在dfn后面

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int N=1e5+5;
int n,m,a[N],dfn[N],top[N],tim,h[N],dep[N],fa[N],siz[N],son[N],cnt,head[N],lst1,lst2;
struct Edge{ int to,next; }e[N<<1]; void add_edge(int u,int v){ e[++cnt]={v,head[u]},head[u]=cnt; }
struct node{
	int l,r; mutable int v;
	bool operator<(const node &x)const{
		return l<x.l;
	}
}; set<node>s;
#define IT set<node>::iterator
IT split(int x){
	if(x>n) return s.end();
	IT it=--s.upper_bound({x,0,0});
	if(it->l==x) return it;
	int l=it->l,r=it->r,v=it->v;
	s.erase(it),s.insert({l,x-1,v});
	return s.insert({x,r,v}).first;
}
void assign(int l,int r,int v){
	IT itr=split(r+1),itl=split(l);
	s.erase(itl,itr),s.insert({l,r,v});
}
int ask(int l,int r,int &lst,int edlst){ int ret=0; IT itr=split(r+1),itl=split(l);
	for(;itl!=itr&&itr!=s.begin();) --itr,ret+=itr->v!=lst,lst=itr->v; return ret-(lst==edlst);
}
void dfs1(int u){ siz[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to; if(v==fa[u]) continue;
		dep[v]=dep[u]+1,fa[v]=u,dfs1(v),siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int tp){
	h[dfn[u]=++tim]=u,top[u]=tp;
	if(son[u]) dfs2(son[u],tp);
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to; if(v==fa[u]||
		v==son[u]) continue; dfs2(v,v);
	}
}
void _set(){
	for(int i=1;i<=n;){ int j=i+1;
		while(j<=n&&a[h[i]]==a[h[j]]) j++;
		s.insert({i,j-1,a[h[i]]}),i=j;
	}
}
void modify(int u,int v,int c){
	while(top[u]^top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		assign(dfn[top[u]],dfn[u],c),u=fa[top[u]];
	} if(dep[u]>dep[v]) swap(u,v); assign(dfn[u],dfn[v],c);
}
int query(int u,int v){ int ret=0; lst1=lst2=0;
	while(top[u]^top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v),swap(lst1,lst2);
		ret+=ask(dfn[top[u]],dfn[u],lst1,0),u=fa[top[u]];
	} if(dep[u]>dep[v]) swap(u,v),swap(lst1,lst2);
	return ret+ask(dfn[u],dfn[v],lst2,lst1);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),
		add_edge(u,v),add_edge(v,u);
	dfs1(1),dfs2(1,1),_set(); char op[2];
	for(int i=1,u,v,c;i<=m;i++){
		scanf("%s%d%d",op,&u,&v);
		if(op[0]=='C') scanf("%d",&c),modify(u,v,c);
		else printf("%d\n",query(u,v));
	} return 0;
｝