题目分析

本题要求处理树上路径颜色计数问题，涉及动态修改节点颜色和查询路径上特定颜色的数量。由于路径查询和动态修改的需求，直接使用树链剖分+线段树难以处理颜色数量的合并，因此采用颜色独立线段树+子树差分的思路：

• 对每个颜色维护一棵线段树，记录该颜色在子树中的出现次数（通过DFS序范围标记子树）。
• 当修改节点颜色时，在原颜色的线段树中减去该节点子树的贡献，在新颜色的线段树中加上该节点子树的贡献。
• 查询路径上某颜色数量时，通过LCA将路径拆分为两段，利用颜色线段树的前缀和计算结果。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;

/*
由于是路径，想到树剖+线段树，但是颜色个数无法合并，因此不行。  
换个思路，用差分来求，然后把每个颜色弄个线段树，
然后这个颜色的线段树单点代表的是这个点到根有多少这个颜色。    
如果x点加了一个颜色为y的，那么以y这棵树，就再某个范围加1，这个范围是x的子树的DFS序范围；
同理，减少则为-1 。
那么查询u到v路径为x颜色的个数，就在x这棵树上求
sum[ u ]+sum[v]-sum[LCA]-sum[fa[LCA]];
*/

// 线段树节点：存储左右子树和懒标记
struct Node {
    int lson, rson, lazy;
    Node() : lson(0), rson(0), lazy(0) {}
} tree[maxn * 80];

// 查询和修改操作的参数
struct Query {
    char opt[3];
    int u, v, x;
} queries[maxn << 1];

// 树的基本信息：深度、父节点、DFS序、LCA预处理
int dep[maxn], fa[maxn][18], in[maxn], ou[maxn], Log[maxn];
// 颜色映射（离散化）
int a[maxn], rt[maxn * 6];  // rt[x]为颜色x的线段树根节点
// 邻接表
int Laxt[maxn], Next[maxn << 1], To[maxn << 1], cnt = 0;
// DFS序和离散化辅助
int times = 0, b[maxn * 6], tot = 0;

// 邻接表添加边
void addEdge(int u, int v) {
    Next[++cnt] = Laxt[u];
    Laxt[u] = cnt;
    To[cnt] = v;
}

// LCA查询（倍增法）
int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    // 提升u到与v同深度
    for (int i = Log[dep[u] - dep[v]]; i >= 0; --i)
        if (dep[fa[u][i]] >= dep[v])
            u = fa[u][i];
    if (u == v) return u;
    // 一起提升到LCA
    for (int i = 17; i >= 0; --i)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

// DFS计算深度、父节点、DFS序
void dfs(int u, int f) {
    in[u] = ++times;
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for (int i = Laxt[u]; i; i = Next[i])
        if (To[i] != f)
            dfs(To[i], u);
    ou[u] = times;
}

// 线段树懒标记下传
void pushDown(int now) {
    if (tree[now].lazy != 0) {
        if (!tree[now].lson) tree[now].lson = ++cnt;
        if (!tree[now].rson) tree[now].rson = ++cnt;
        tree[tree[now].lson].lazy += tree[now].lazy;
        tree[tree[now].rson].lazy += tree[now].lazy;
        tree[now].lazy = 0;
    }
}

// 线段树区间更新（子树范围加值）
void update(int &now, int L, int R, int l, int r, int val) {
    if (!now) now = ++cnt;
    if (l <= L && r >= R) {
        tree[now].lazy += val;
        return;
    }
    int mid = (L + R) >> 1;
    pushDown(now);
    if (l <= mid) update(tree[now].lson, L, mid, l, r, val);
    if (r > mid) update(tree[now].rson, mid + 1, R, l, r, val);
}

// 线段树单点查询（点值）
int query(int now, int L, int R, int pos) {
    if (!now) return 0;
    if (L == R) return tree[now].lazy;
    int mid = (L + R) >> 1;
    pushDown(now);
    return pos <= mid ? query(tree[now].lson, L, mid, pos) : query(tree[now].rson, mid + 1, R, pos);
}

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    // 预处理Log数组（用于LCA）
    for (int i = 2; i <= N; ++i)
        Log[i] = Log[i >> 1] + 1;
    // 读入初始颜色并离散化
    for (int i = N; i >= 1; --i) {
        scanf("%d", &a[i]);
        b[++tot] = a[i];
    }
    // 读入树边
    for (int i = 1; i < N; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    // 第一次DFS计算DFS序和父节点
    dfs(1, 0);
    // 预处理LCA的倍增表
    for (int j = 1; j <= 17; ++j)
        for (int i = 1; i <= N; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    // 处理查询和修改操作，收集所有颜色值用于离散化
    for (int i = 1; i <= Q; ++i) {
        scanf("%s%d%d", queries[i].opt, &queries[i].u, &queries[i].v);
        if (queries[i].opt[0] == 'Q') {
            scanf("%d", &queries[i].x);
            b[++tot] = queries[i].x;
        } else {
            b[++tot] = queries[i].v;
        }
    }
    // 离散化颜色值
    sort(b + 1, b + tot + 1);
    tot = unique(b + 1, b + tot + 1) - (b + 1);
    for (int i = 1; i <= N; ++i)
        a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
    for (int i = 1; i <= Q; ++i) {
        if (queries[i].opt[0] == 'Q')
            queries[i].x = lower_bound(b + 1, b + tot + 1, queries[i].x) - b;
        else
            queries[i].v = lower_bound(b + 1, b + tot + 1, queries[i].v) - b;
    }
    // 初始化颜色线段树（初始每个节点颜色的子树贡献）
    for (int i = 1; i <= N; ++i)
        update(rt[a[i]], 0, N, in[i], ou[i], 1);
    // 处理每个查询
    for (int i = 1; i <= Q; ++i) {
        int u = queries[i].u, v = queries[i].v;
        if (queries[i].opt[0] == 'C') {  // 修改颜色
            // 原颜色减去贡献
            update(rt[a[u]], 0, N, in[u], ou[u], -1);
            // 更新颜色
            a[u] = v;
            // 新颜色加上贡献
            update(rt[a[u]], 0, N, in[u], ou[u], 1);
        } else {  // 查询颜色
            int x = queries[i].x;
            int lca = LCA(u, v);
            // 计算路径u到v的颜色x数量：sum(u) + sum(v) - sum(lca) - sum(fa(lca))
            int res = query(rt[x], 0, N, in[u]) + query(rt[x], 0, N, in[v]) - query(rt[x], 0, N, in[lca]) - query(rt[x], 0, N, in[fa[lca][0]]);
            printf("%d\n", res);
        }
    }
    return 0;
}

/*
由于是路径，想到树剖+线段树，但是颜色个数无法合并，因此不行。  
换个思路，用差分来求，然后把每个颜色弄个线段树，
然后这个颜色的线段树单点代表的是这个点到根有多少这个颜色。    
如果x点加了一个颜色为y的，那么以y这棵树，就再某个范围加1，这个范围是x的子树的DFS序范围；
同理，减少则为-1 。
那么查询u到v路径为x颜色的个数，就在x这棵树上求
sum[ u ]+sum[v]-sum[LCA]-sum[fa[LCA]];

*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=100010;
struct in{
    int lson,rson,lazy;
    in(){lson=rson=lazy=0;}
}s[maxn*80];
struct qqq{
    char opt[3]; int u,v,x;
}q[maxn<<1];
int dep[maxn],a[maxn],rt[maxn*6],fa[maxn][18],in[maxn],ou[maxn],Log[maxn];
int Laxt[maxn],Next[maxn<<1],To[maxn<<1],cnt,times,b[maxn*6],tot;
void add(int u,int v){
    Next[++cnt]=Laxt[ u ]; Laxt[ u ]=cnt; To[cnt]=v;
}
int LCA(int u,int v){
    if(dep[ u ]<dep[v]) swap(u,v);
    for(int i=Log[dep[ u ]-dep[v]];i>=0;i--)
      if(dep[fa[ u ][i]]>=dep[v]) u=fa[ u ][i];
    if(u==v) return u;
    for(int i=17;i>=0;i--)
      if(fa[ u ][i]!=fa[v][i]) u=fa[ u ][i],v=fa[v][i];
    return fa[ u ][0];
}
void dfs(int u,int f){
    in[ u ]=++times;dep[ u ]=dep[f]+1;
    for(int i=Laxt[ u ];i;i=Next[i])
      if(To[i]!=f) dfs(To[i],u);
    ou[ u ]=times; fa[ u ][0]=f;
}
void pushdown(int Now){
    if(s[Now].lazy!=0){
        if(!s[Now].lson) s[Now].lson=++cnt;
        if(!s[Now].rson) s[Now].rson=++cnt;
        s[s[Now].lson].lazy+=s[Now].lazy;
        s[s[Now].rson].lazy+=s[Now].lazy;
        s[Now].lazy=0;
    }
}
void addnum(int &Now,int L,int R,int l,int r,int add){
    if(!Now) Now=++cnt;
    if(l<=L&&r>=R){ s[Now].lazy+=add; return ; }
    int Mid=(L+R)>>1; pushdown(Now);
    if(l<=Mid)  addnum(s[Now].lson,L,Mid,l,r,add);
    if(r>Mid)  addnum(s[Now].rson,Mid+1,R,l,r,add);
}
int query(int Now,int L,int R,int pos){
    if(!Now) return 0;
    if(L==R) return s[Now].lazy;
    int Mid=(L+R)>>1; pushdown(Now);
    if(pos<=Mid) return query(s[Now].lson,L,Mid,pos);
    return query(s[Now].rson,Mid+1,R,pos);
}
int main()
{
    int N,Q,u,v,x;
    scanf("%d%d",&N,&Q);  rep(i,2,N)   Log[i]=Log[i>>1]+1;
    rep(i,1,N) scanf("%d",&a[i]),b[++tot]=a[i];
    rep(i,1,N-1){
        scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    dfs(1,0); cnt=0;
    rep(j,1,17)
     rep(i,1,N){
        fa[i][j]=fa[fa[i][j-1]][j-1];
    }
    rep(i,1,Q){
        scanf("%s%d%d",q[i].opt,&q[i].u,&q[i].v);
        if(q[i].opt[0]=='Q') scanf("%d",&q[i].x),b[++tot]=q[i].x;
        else b[++tot]=q[i].v;
    }
    sort(b+1,b+tot+1); tot=unique(b+1,b+tot+1)-(b+1);
    rep(i,1,N) a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    rep(i,1,Q) {
        if(q[i].opt[0]=='Q') q[i].x=lower_bound(b+1,b+tot+1,q[i].x)-b;
        else q[i].v=lower_bound(b+1,b+tot+1,q[i].v)-b;
    }
    rep(i,1,N) addnum(rt[a[i]],0,N,in[i],ou[i],1);
    rep(i,1,Q){
        u=q[i].u; v=q[i].v;
        if(q[i].opt[0]=='C'){
           addnum(rt[a[ u ]],0,N,in[ u ],ou[ u ],-1); a[ u ]=v;
           addnum(rt[a[ u ]],0,N,in[ u ],ou[ u ],1);
        }
        else {
           x=q[i].x;
           int Lca=LCA(u,v);
           int res=query(rt[x],0,N,in[ u ]);
           res+=query(rt[x],0,N,in[v]);
           res-=query(rt[x],0,N,in[Lca]);
           res-=query(rt[x],0,N,in[fa[Lca][0]]);
           printf("%d\n",res);
        }
    }
    return 0;
}