输出格式
对于每个询问操作，输出一行答案。

输入输出样例
输入 #1复制
6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5
输出 #1复制
3
1
2

这道题真的是深有感触，当年写树剖一直过不了，也找不到bug，后来不了了之。然后现在换成LCT就好写多了，考虑的东西少了点。

我们用LCT维护链，当前节点颜色，当前表示的链的左颜色，右颜色，当前链的颜色段数量。然后转移即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
int n,m;
int cnt,st[N];
struct node{int ch[2],fa,res,lc,rc,lazy,col,re;}t[N];
inline void push_up(int p){
	t[p].lc=ls(p)?t[ls(p)].lc:t[p].col;
	t[p].rc=rs(p)?t[rs(p)].rc:t[p].col; 
	if(ls(p)&&rs(p)){
		t[p].res=t[ls(p)].res+t[rs(p)].res+1;
		if(t[ls(p)].rc==t[p].col)	t[p].res--;
		if(t[rs(p)].lc==t[p].col)	t[p].res--;
	}
	if(ls(p)&&!rs(p))	t[p].res=t[ls(p)].res+1-(t[ls(p)].rc==t[p].col);
	if(!ls(p)&&rs(p))	t[p].res=t[rs(p)].res+1-(t[rs(p)].lc==t[p].col);
	if(!ls(p)&&!rs(p))	t[p].res=1;
}
inline void push_re(int p){
	swap(ls(p),rs(p)); swap(t[p].lc,t[p].rc);	t[p].re^=1;
}
inline void pushc(int p,int c){
	t[p].lc=t[p].rc=t[p].col=t[p].lazy=c; t[p].res=1;
}
inline void push_down(int p){	
	if(t[p].lazy){
		if(ls(p)) pushc(ls(p),t[p].lazy); if(rs(p)) pushc(rs(p),t[p].lazy);
		t[p].lazy=0;
	}
	if(t[p].re){
		if(ls(p))	push_re(ls(p));	if(rs(p))	push_re(rs(p)); t[p].re^=1;
	}
}
inline bool isroot(int x){return ls(t[x].fa)!=x&&rs(t[x].fa)!=x;}
inline void rotate(int x){
	int y=t[x].fa,z=t[y].fa,k=rs(y)==x,w=t[x].ch[!k];
	if(!isroot(y))	t[z].ch[rs(z)==y]=x; t[x].ch[!k]=y; t[y].ch[k]=w;
	if(w)	t[w].fa=y; t[y].fa=x; t[x].fa=z;	push_up(y);
}
inline void splay(int x){
	cnt=1;	st[cnt]=x; int y=x;
	while(!isroot(y))	st[++cnt]=y=t[y].fa;
	while(cnt)	push_down(st[cnt--]);
	while(!isroot(x)){
		int y=t[x].fa,z=t[y].fa;
		if(!isroot(y))	rotate((ls(y)==x)^(ls(z)==y)?x:y); rotate(x);
	}push_up(x);
}
inline void access(int x){
	for(int y=0;x;x=t[y=x].fa) splay(x),rs(x)=y,push_up(x); 
}
inline void makeroot(int x){
	access(x); splay(x); push_re(x);
}
inline int find(int x){
	access(x); splay(x); while(ls(x)) push_down(x),x=ls(x); 
	splay(x);	return x;
}
inline void split(int x,int y){
	makeroot(x); access(y); splay(y);
}
inline void link(int x,int y){
	makeroot(x); 	t[x].fa=y;
}
inline void cut(int x,int y){
	makeroot(x); 
	if(find(y)==x&&t[y].fa==x&&!ls(y)) t[y].fa=rs(x)=0,push_up(x);
}
signed main(){
	cin>>n>>m;
	for(int i=1,x;i<=n;i++)	
		scanf("%d",&x),t[i].lc=t[i].rc=t[i].col=x,t[i].res=1;
	for(int i=1,a,b;i<n;i++)	scanf("%d %d",&a,&b),link(a,b);
	char op[2]; int a,b,c;
	while(m--){
		scanf("%s %d %d",op,&a,&b);
		if(op[0]=='C'){
			scanf("%d",&c);	split(a,b);	pushc(b,c);
		}else{
			split(a,b);	printf("%d\n",t[b].res);
		}
	}
	return 0;
}