题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2243
///#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
const int maxn =1e5+5;
const int mod=9999991;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}/*
题目意思很简单，
查询书上两点路径不同连续颜色段数量。树链剖分轻重链，
然后用线段树维护数量，
通过lca维护区间性质，这道题细节就是细节比较多，
因为要判断是否多加了数量要特地单点查询颜色，
懒惰标记也要下压，具体思路还是很清晰的。通过线段树操作，维护修改和查询。
时间复杂度：O(nlogn*logn)
*/struct node{int u,nxt;///当前节点和下一个节点和颜色
}e[maxn<<1];///边的数组
int head[maxn],tot,id;
void add(int x,int y){e[tot]=node{y,head[x]};head[x]=tot++;
}int son[maxn],dep[maxn],siz[maxn],fa[maxn];///节点大小数组，下一个son位置数组void init(){mst(head,-1),mst(son,0);tot=id=dep[1]=fa[1]=0;
}void dfs1(int u){///深度数组，父节点数组siz[u]=1;for(int i=head[u];~i;i=e[i].nxt){int v=e[i].u;if(v!=fa[u]){dep[v]=dep[u]+1;fa[v]=u;dfs1(v);siz[u]+=siz[v];if(siz[son[u]]<siz[v]) son[u]=v;///建立链接}}
}int top[maxn],idx[maxn];
void dfs2(int u,int tp){top[u]=tp;idx[u]=++id;if(son[u]) dfs2(son[u],tp);for(int i=head[u];~i;i=e[i].nxt){int v=e[i].u;if(v==son[u] || v==fa[u]) continue;dfs2(v,v);}
}///求lca
int lca(int u,int v){int tp1=top[u],tp2=top[v];while(tp1!=tp2){if(dep[tp1]<dep[tp2]){swap(u,v);swap(tp1,tp2);}u=fa[tp1];tp1=top[u];}return dep[u]>dep[v]?v:u;
}int n,m,a,b;
int c[maxn];
///线段树结构
int tree[maxn<<2],lc[maxn<<2],rc[maxn<<2],lazy[maxn<<2];///区间的左颜色和右颜色
void push_up(lrt){lc[rt]=lc[rt<<1],rc[rt]=rc[rt<<1|1];tree[rt]=tree[rt<<1]+tree[rt<<1|1];if(lc[rt<<1|1]==rc[rt<<1]) tree[rt]--;
}void push_down(lrt){if(lazy[rt]==-1||l==r) {lazy[rt]=-1; return;}lc[rt<<1]=rc[rt<<1]=lc[rt<<1|1]=rc[rt<<1|1]=lazy[rt];tree[rt<<1]=tree[rt<<1|1]=1;lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];lazy[rt]=-1;
}void build(lrt){lazy[rt]=-1;tree[rt]=1;if(l==r) return;int mid=l+r>>1;build(lson),build(rson),push_up(root);
}void update(lrt,int L,int R,int v){if(L<=l&&r<=R){tree[rt]=1;lc[rt]=rc[rt]=lazy[rt]=v;return ;}int mid=l+r>>1;push_down(root);if(L<=mid) update(lson,L,R,v);if(mid<R) update(rson,L,R,v);push_up(root);
}int query(lrt,int L,int R){if(L<=l&&r<=R) return tree[rt];push_down(root);int mid=l+r>>1,ans=0,flag=0;if(L<=mid) ans+=query(lson,L,R),flag++;if(mid<R) ans+=query(rson,L,R),flag++;if(flag==2){if(lc[rt<<1|1]==rc[rt<<1]) ans--;}return ans;
}void change(int u,int v,int z){///v已经是祖先了int tpu=top[u],tpv=top[v];while(tpu!=tpv){update(1,n,1,idx[tpu],idx[u],z);u=fa[tpu];tpu=top[u];}update(1,n,1,idx[v],idx[u],z);
}int get_c(lrt,int x)
{if(l==r) return lc[rt];push_down(root);int mid=l+r>>1;if(x<=mid) return get_c(lson,x);if(mid<x) return get_c(rson,x);
}int get_color(int u,int v)///返回u到v路径上的颜色数量,u在底下
{int tpu=top[u],tpv=top[v],ans=0;while(tpu!=tpv){ans+=query(1,n,1,idx[tpu],idx[u]);if(get_c(1,n,1,idx[tpu])==get_c(1,n,1,idx[fa[tpu]])) ans--;u=fa[tpu];tpu=top[u];}ans+=query(1,n,1,idx[v],idx[u]);return ans;
}int q,u,v,cr;
char op[5];int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&c[i]);init();///初始化链for(int i=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b),add(b,a);}dfs1(1),dfs2(1,1),build(1,n,1);for(int i=1;i<=n;i++) update(1,n,1,idx[i],idx[i],c[i]);///for(int i=1;i<=n;i++) cout<<idx[i]<<" ";puts("");while(m--){scanf("%s",op);if(op[0]=='C'){scanf("%d%d%d",&u,&v,&cr);int x=lca(u,v);change(u,x,cr);change(v,x,cr);}else{scanf("%d%d",&u,&v);int x=lca(u,v);printf("%d\n",get_color(u,x)+get_color(v,x)-1);}}return 0;
}