思路:区间修改,线段用来维护区间颜色段的个数,区间左端点颜***间右端点颜色。
查询的时候,因为把一条路径分成若干次区间查询,我们必须维护左右端点的颜色。
例如:查询U-V时:U和V都可能会跳,每次跳后必须记录端点的颜色pos1, pos2。例如这次查询:

是查询u-x。根据树链剖分,那么x的新编号>u的新编号。
所有在线段树上查询时是从x->u。查询颜色的个数,并且维护Lc和Rc为这一段的左右端点的颜色,并且判断Rc的颜色是否和pos1相同,如果相同颜色数-1。
并且pos=Lc的颜色。

如果跳v那么我们交换pos1和pos2.那么每次就是和pos1比较了。

如果最后一次跳。我们要注意:

要比较Lc和pos1,Rc和pos2。

线段树内部不同情区间查询也要注意比较端点颜色。

//#include <bits/stdc++.h>
//#define Rint register int
//using namespace std;
//
//int main(){
//
// srand(time(0));
// int n=rand()%5+5, m=rand()%7+1;
// printf("%d %d\n", n, m);
// for(int i=1; i<=n; i++){
// cout<<rand()%4+1<<" ";
// }
// cout<<endl;
// for(int i=2; i<=n; i++){
// cout<<i<<" "<<rand()%(i-1)+1<<endl;
// }
// for(int i=1; i<=m; i++){
// int k, a, b, c;
// k=rand()%2;
// if(k){
// a=rand()%(n)+1;
// b=rand()%(n)+1;
// c=rand()%3+1;
// cout<<"C "<<a<<" "<<b<<" "<<c<<endl;
// }
// else{
// a=rand()%(n)+1;
// b=rand()%(n)+1;
// cout<<"Q "<<a<<" "<<b<<endl;
// }
// }
//
// return 0;
//}
#include <bits/stdc++.h>
#define Rint register int
using namespace std;

#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)

const int maxn=1000005;
int n,m;
//见题意
int tot,head[maxn],nex[maxn],to[maxn], w[maxn], wt[maxn];
//链式前向星数组,w[]、wt[]初始点权数组
int lc[maxn<<2], rc[maxn<<2], sc[maxn<<2], laz[maxn<<2];
//线段树数组 左端颜色 右端颜***间标记
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];
//son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点
int pos1, pos2, Lc, Rc,res;
//链左端颜色 链右端颜色 查询答案

inline void add(int x,int y){//链式前向星加边
    to[++tot]=y;
    nex[tot]=head[x];
    head[x]=tot;
}
//-------------------------------------- 以下为线段树

inline void build(int rt,int l,int r){
    if(l==r){
        lc[rt]=rc[rt]=wt[l];
        sc[rt]=1;
        laz[rt]=0;
        return;
    }
    build(lson);
    build(rson);
    sc[rt]=sc[rt<<1]+sc[rt<<1|1];
    if(rc[rt<<1]==lc[rt<<1|1]){
        sc[rt]--;
    }
    lc[rt]=lc[rt<<1];
    rc[rt]=rc[rt<<1|1];
}

void down(int rt){
    if(laz[rt]){
        laz[rt<<1]=laz[rt<<1|1]=laz[rt];
        sc[rt<<1]=sc[rt<<1|1]=sc[rt];
        lc[rt<<1]=lc[rt<<1|1]=rc[rt<<1]=rc[rt<<1|1]=laz[rt];
        laz[rt]=0;
    }
}

inline void update(int rt, int l, int r, int L, int R, int k){
    if(L<=l&&r<=R){
        laz[rt]=lc[rt]=rc[rt]=k;
        sc[rt]=1;
        //cout<<"L "<<l<<" "<<r<<" "<<lc[rt]<<" "<<rc[rt]<<" "<<sc[rt]<<endl;
        return;
    }
    else{

        down(rt);
        if(L<=mid)update(lson,L,R,k);
        if(R>mid)update(rson,L,R,k);
        sc[rt]=sc[rt<<1]+sc[rt<<1|1];
        if(rc[rt<<1]==lc[rt<<1|1]){
            sc[rt]--;
        }
        lc[rt]=lc[rt<<1];
        rc[rt]=rc[rt<<1|1];
        //cout<<"L "<<l<<" "<<r<<" "<<lc[rt]<<" "<<rc[rt]<<" "<<sc[rt]<<endl;
    }
}

inline void query(int rt,int l,int r,int L,int R){

    if(L<=l&&r<=R){
        res+=sc[rt];
        if(lc[rt]==Rc){
            res--;
        }
        if(L==l){
            Lc=lc[rt];
        }
        Rc=rc[rt];

        return;
    }
    else{
        if(laz[rt])down(rt);
        if(L<=mid)query(lson,L,R);
        if(R>mid)query(rson,L,R);
    }

}
/* 7 100 1 1 1 1 1 1 1 1 2 2 3 3 5 3 4 2 6 1 7 C 1 2 2 Q 7 3 */

//-------------------------------------- 以上为线段树
inline int Q(int x, int y){
    pos1=pos2=0;res=0;
    while(top[x]!=top[y]){//当两个点不在同一条链上
        if(dep[top[x]]<dep[top[y]])swap(x,y), swap(pos1,pos2);//把x点改为所在链顶端的深度更深的那个点
        Lc=Rc=0;
        query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
        x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
        if(Rc==pos1){
            res--;
        }
        pos1=Lc;

    }
    //直到两个点处于一条链上
    Lc=Rc=0;
    if(dep[x]>dep[y])swap(x,y), swap(pos1,pos2);//把x点深度更深的那个点
    query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可
    if(Lc==pos1){
        res--;
    }
    if(Rc==pos2){
        res--;
    }
    return res;
}

inline void U(int x, int y, int k){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,1,n,id[x],id[y],k);
}

//-------------------------------------- 以下为模板
inline void dfs1(int x,int f,int deep){
    dep[x]=deep;
    fa[x]=f;
    siz[x]=1;
    int maxson=-1;
    for(Rint i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>maxson)son[x]=y,maxson=siz[y];
    }
}

inline void dfs2(int x,int topf){
    id[x]=++cnt;
    top[x]=topf;
    //cout<<x<<" ; "<<cnt<<endl;
    wt[cnt]=w[x];//把每个点的初始值赋到新编号上来
    if(!son[x])return;
    dfs2(son[x],topf);
    for(Rint i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%d", &w[i]);
    }
    for(Rint i=1;i<n;i++){
        int a,b;
        scanf("%d%d", &a, &b);
        add(a,b);add(b,a);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n);
    while(m--){
        char s[5];
        int a, b, c;
        scanf("%s", s);
        if(s[0]=='C'){
            scanf("%d%d%d", &a, &b, &c);
            U(a, b, c);
        }
        else{
            int a, b;
            scanf("%d%d", &a, &b);
            printf("%d\n", Q(a, b));
        }
    }
}

/* 6 6 4 2 2 4 3 1 2 1 3 1 4 2 5 3 6 3 C 6 2 1 C 1 2 3 Q 4 3 */