T1
考虑树剖，线段树维护区间内的颜色段数和每个点的颜色。
查询时每次遇到不同链判断相邻的颜色是否相同，如果相同将答案减一。
#include<bits/stdc++.h>
#define N 100005
#define getc getchar
using namespace std;
int n,m;
class SGT{#define l(i) ((i)<<1)#define r(i) ((i)<<1|1)#define c(i) tr[i].cnt#define t(i) tr[i].tag#define lc(i) tr[i].lcol#define rc(i) tr[i].rcolprivate:struct node{int cnt,tag,lcol,rcol;}tr[N<<2];void up(int x){lc(x)=lc(l(x)),rc(x)=rc(r(x));c(x)=c(l(x))+c(r(x))-(rc(l(x))==lc(r(x)));}void down(int x){if(!t(x)) return;c(l(x))=c(r(x))=1;t(l(x))=t(r(x))=t(x);lc(l(x))=lc(r(x))=t(x);rc(l(x))=rc(r(x))=t(x);t(x)=0;}public:void upd(int ql,int qr,int v,int x=1,int l=1,int r=n){if(ql<=l&&qr>=r) return t(x)=lc(x)=rc(x)=v,c(x)=1,void();int mid=l+r>>1;down(x);if(ql<=mid) upd(ql,qr,v,l(x),l,mid);if(qr>mid) upd(ql,qr,v,r(x),mid+1,r);up(x);}int query(int ql,int qr,int x=1,int l=1,int r=n){if(ql<=l&&qr>=r) return c(x);int mid=l+r>>1;down(x);if(ql<=mid&&qr>mid)return query(ql,qr,l(x),l,mid)+query(ql,qr,r(x),mid+1,r)-(rc(l(x))==lc(r(x)));if(ql<=mid) return query(ql,qr,l(x),l,mid);if(qr>mid) return query(ql,qr,r(x),mid+1,r);return 0;}int get(int p,int x=1,int l=1,int r=n){if(l==r) return t(x);int mid=l+r>>1;down(x);if(p<=mid) return get(p,l(x),l,mid);return get(p,r(x),mid+1,r);}#undef l#undef r#undef c#undef t#undef lc#undef rc
}tr;
vector<int>s[N];
int dfn[N],top[N],hson[N];
int idx,a[N],fa[N],siz[N],dep[N];
void dfs1(int x){dep[x]=dep[fa[x]]+(siz[x]=1);for(auto p:s[x])if(p^fa[x]){fa[p]=x,dfs1(p);siz[x]+=siz[p];if(siz[p]>siz[hson[x]])hson[x]=p;}
}
void dfs2(int x,int t){dfn[x]=++idx;top[x]=t;if(hson[x]) dfs2(hson[x],top[x]);for(auto p:s[x])if(p^fa[x]&&p^hson[x])dfs2(p,p);
}
void upd(int u,int v,int c){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);tr.upd(dfn[top[u]],dfn[u],c),u=fa[top[u]];}if(dep[u]>dep[v]) swap(u,v);tr.upd(dfn[u],dfn[v],c);
}
int query(int u,int v){int res=0;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);res+=tr.query(dfn[top[u]],dfn[u]);res-=tr.get(dfn[top[u]])==tr.get(dfn[u=fa[top[u]]]);}if(dep[u]>dep[v]) swap(u,v);return res+tr.query(dfn[u],dfn[v]);
}
int main(){scanf("%d%d",&n,&m);for(int i=1,x;i<=n;i++) scanf("%d",a+i);for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),s[u].emplace_back(v),s[v].emplace_back(u);dfs1(1),dfs2(1,1);for(int i=1,x;i<=n;i++)tr.upd(dfn[i],dfn[i],a[i]);while(m--){char c=getc();int a,b,v;while(c!='C'&&c!='Q') c=getc();if(c=='C')scanf("%d%d%d",&a,&b,&v),upd(a,b,v);if(c=='Q')scanf("%d%d",&a,&b),printf("%d\n",query(a,b));}return 0;
}