1. 题目

LUOGU 传送门=￣ω￣=
BZOJ 传送门=￣ω￣=

2. 题解

没什么好说的，树链剖分模板题
线段树记录区间左右端点颜色，合并区间的时候看左区间的右端点和右区间的左端点是否相同，相同则颜色段数-1

代码：

#include <bits/stdc++.h>
#define NS (100005)
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c)&&c!='-')c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,arr[NS],fa[NS],siz[NS],dep[NS],pos[NS],top[NS],cnt,w[NS];
char opt[5];
vector<int> g[100005];
struct N{int l,r,d,f,lc,rc;N(){l=r=d=lc=rc=0,f=-1;}}e[NS<<2];
void update(int a)
{
    e[a].d=e[LS(a)].d+e[RS(a)].d-(e[LS(a)].rc==e[RS(a)].lc);
    e[a].lc=e[LS(a)].lc,e[a].rc=e[RS(a)].rc;
}
void pdown(int a)
{
    e[LS(a)].lc=e[LS(a)].rc=e[RS(a)].lc=e[RS(a)].rc=
    e[LS(a)].f=e[RS(a)].f=e[a].f,e[LS(a)].d=e[RS(a)].d=1,e[a].f=-1;
}
void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r;
    if(l==r){e[a].d=1,e[a].lc=e[a].rc=w[l];return;}
    build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a)),update(a);
}
void change(int l,int r,int k,int a)
{
    if(l<=e[a].l&&e[a].r<=r){e[a].lc=e[a].rc=e[a].f=k,e[a].d=1;return;}
    if(e[a].f!=-1)pdown(a);
    if(l<=((e[a].l+e[a].r)>>1))change(l,r,k,LS(a));
    if(r>((e[a].l+e[a].r)>>1))change(l,r,k,RS(a));
    update(a);
}
int query(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].d;
    if(e[a].f!=-1)pdown(a);
    int tot=0;
    if(l<=((e[a].l+e[a].r)>>1))tot+=query(l,r,LS(a));
    if(r>((e[a].l+e[a].r)>>1))tot+=query(l,r,RS(a));
    tot-=
        (e[LS(a)].rc==e[RS(a)].lc&&l<=((e[a].l+e[a].r)>>1)&&r>((e[a].l+e[a].r)>>1));
    return tot;
}
pair<int,int> query_c(int l,int r,int a)
{
    pair<int,int> tot;
    if(l<=e[a].l&&e[a].r<=r){tot=make_pair(e[a].lc,e[a].rc);return tot;}
    if(e[a].f!=-1)pdown(a);
    if(l<=((e[a].l+e[a].r)>>1))tot=query_c(l,r,LS(a));
    if(r>((e[a].l+e[a].r)>>1))
    {
        if(!(l<=((e[a].l+e[a].r)>>1)))tot=query_c(l,r,RS(a));
        else tot.second=query_c(l,r,RS(a)).second;
    }
    return tot;
}
void dfs1(int u)
{
    siz[u]=1,dep[u]=dep[fa[u]]+1;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u])fa[g[u][i]]=u,dfs1(g[u][i]),siz[u]+=siz[g[u][i]];
}
void dfs2(int u)
{
    pos[u]=cnt++;
    int nxt=0,maxn=0;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&siz[g[u][i]]>maxn)nxt=g[u][i],maxn=siz[g[u][i]];
    if(!nxt)return;
    top[nxt]=top[u],dfs2(nxt);
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&g[u][i]!=nxt)top[g[u][i]]=g[u][i],dfs2(g[u][i]);
}
void work1(int a,int b,int c)
{
    while(top[a]!=top[b])
    {
        if(dep[top[a]]>dep[top[b]])swap(a,b);
        change(pos[top[b]],pos[b],c,1),b=fa[top[b]];
    }
    if(dep[a]>dep[b])swap(a,b);
    change(pos[a],pos[b],c,1);
}
void work2(int a,int b)
{
    pair<int,int> ca=make_pair(-1,-1),cb=make_pair(-1,-1),cc;int tot=0;
    while(top[a]!=top[b])
    {
        if(dep[top[a]]>dep[top[b]])swap(a,b),swap(ca,cb);
        tot+=query(pos[top[b]],pos[b],1),cc=query_c(pos[top[b]],pos[b],1);
        tot-=(cb.first==cc.second),cb=cc,b=fa[top[b]];
    }
    if(dep[a]>dep[b])swap(a,b),swap(ca,cb);
    tot+=query(pos[a],pos[b],1),cc=query_c(pos[a],pos[b],1);
    tot-=(cc.first==ca.first)+(cc.second==cb.first);
    printf("%d\n",tot);
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)IN(arr[i]);
    for(int i=1,a,b;i<n;i++)IN(a),IN(b),g[a].push_back(b),g[b].push_back(a);
    dfs1(1),top[1]=1,dfs2(1);
    for(int i=1;i<=n;i++)w[pos[i]]=arr[i];
    build(0,cnt-1,1);
    for(int i=1,a,b,c;i<=m;i++)
        if(scanf("%s",opt),IN(a),IN(b),opt[0]=='C')IN(c),work1(a,b,c);
        else work2(a,b);
    return 0;
}