Description

给定一棵有n个节点的无根树和m个操作，操作有2类：

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

Input

第一行包含2个整数n和m，分别表示节点数和操作数；

第二行包含n个正整数表示n个节点的初始颜色

下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面 行每行描述一个操作：

“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

Output

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

Sample Input
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

Sample Output
3

1

2

HINT

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

解法：尴尬尴尬尴尬尴尬。。。又因为小错误卡得一逼。。。状态不对，感觉要死掉了。。。。。这题就是裸

的树链剖分，线段树维护区间左端点颜色，右端点颜色和整个区间分成的段数，然后区间更新即可。但是在轻

重链跳的时候也要判断当前练和下一条链的端点相邻的地方是否颜色相同，然后更新。

///BZOJ 2243 #include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, cnt, tim, head[maxn], dep[maxn], son[maxn], top[maxn], tid[maxn], siz[maxn], num[maxn], fa[maxn][18], Rank[maxn];
bool vis[maxn];
struct seg{
    int l,r,lc,rc,s,tag;
}tree[maxn*4];
struct edge{
    int to,next;
}E[maxn*2];
void init(){
    memset(head,-1,sizeof(head));
    memset(son,-1,sizeof(son));
    memset(vis, 0, sizeof(vis));
    cnt=tim=0;
}
void addedge(int u,int v){
    E[cnt].to=v,E[cnt].next=head[u],head[u]=cnt++;
}
void dfs1(int x){
    vis[x]=1;
    siz[x]=1;
    //if(x==1) fa[x][0]=1;
    for(int i=1; i<=17; i++){
        if(dep[x]<(1<<i)) break;
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(int i=head[x]; ~i; i=E[i].next){
        int to=E[i].to;
        if(vis[to]) continue;
        dep[to]=dep[x]+1;
        fa[to][0]=x;
        dfs1(to);
        siz[x]+=siz[to];
        if(son[x]==-1||siz[to]>siz[son[x]]) son[x]=to;
    }
}
void dfs2(int u, int tp){
    top[u]=tp;
    tid[u]=++tim;
    Rank[tid[u]]=u;
    if(son[u]==-1) return;
    dfs2(son[u],tp);
    for(int i=head[u];~i;i=E[i].next){
        int v=E[i].to;
        if(v!=son[u]&&v!=fa[u][0]){
            dfs2(v,v);
        }
    }
}
int lca(int x, int y){
    if(dep[x]<dep[y]) swap(x,y);
    int t=dep[x]-dep[y];
    for(int i=0; i<=17; i++){
        if(t&(1<<i)) x=fa[x][i];
    }
    for(int i=17;i>=0;i--)
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
    }
    if(x==y) return x;
    return fa[x][0];
}
void pushup(int rt){
    tree[rt].lc=tree[rt*2].lc, tree[rt].rc=tree[rt*2+1].rc;
    if(tree[rt*2].rc^tree[rt*2+1].lc) tree[rt].s=tree[rt*2].s+tree[rt*2+1].s;
    else tree[rt].s=tree[rt*2].s+tree[rt*2+1].s-1;
}
void pushdown(int rt){
    if(tree[rt].tag!=-1){
        tree[rt*2].s=tree[rt*2+1].s=1;
        tree[rt*2].tag=tree[rt*2+1].tag=tree[rt].tag;
        tree[rt*2].lc=tree[rt*2+1].lc=tree[rt].tag;
        tree[rt*2].rc=tree[rt*2+1].rc=tree[rt].tag;
        tree[rt].tag=-1;
    }
}
void Build(int l, int r, int rt){
    tree[rt].l=l,tree[rt].r=r;
    tree[rt].tag=-1;
    if(l==r){
        tree[rt].lc=tree[rt].rc=num[Rank[l]];
        tree[rt].s=1;
        return ;
    }
    int mid=(l+r)/2;
    Build(l,mid,rt*2);
    Build(mid+1,r,rt*2+1);
    pushup(rt);
}
void build(int l, int r, int rt){
    tree[rt].l=l,tree[rt].r=r;
    tree[rt].s=1;
    tree[rt].tag=-1;
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
}
void update(int L, int R, int v, int rt){
    if(L<=tree[rt].l&&tree[rt].r<=R){
        tree[rt].lc=tree[rt].rc=tree[rt].tag=v;
        tree[rt].s=1;
        return;
    }
    pushdown(rt);
    int mid=(tree[rt].l+tree[rt].r)/2;
    if(R<=mid) update(L,R,v,rt*2);
    else if(L>mid) update(L,R,v,rt*2+1);
    else{
        update(L,mid,v,rt*2);
        update(mid+1,R,v,rt*2+1);
    }
    pushup(rt);
}
int query(int L, int R, int rt){
    if(L<=tree[rt].l&&tree[rt].r<=R){
        return tree[rt].s;
    }
    pushdown(rt);
    int mid=(tree[rt].l+tree[rt].r)/2;
    if(R<=mid) return query(L,R,rt*2);
    else if(L>mid) return query(L,R,rt*2+1);
    else{
        int tmp=1;
        if(tree[rt*2].rc^tree[rt*2+1].lc) tmp=0;
        return query(L,mid,rt*2)+query(mid+1,R,rt*2+1)-tmp;
    }
}
int getv(int pos, int rt){
    if(tree[rt].l==tree[rt].r) return tree[rt].lc;
    pushdown(rt);
    int mid=(tree[rt].l+tree[rt].r)/2;
    if(pos<=mid) return getv(pos,rt*2);
    else return getv(pos,rt*2+1);
    pushup(rt);
}
int querysum(int x, int y){
    int sum=0;
    while(top[x]!=top[y]){
        sum+=query(tid[top[x]],tid[x],1);
        if(getv(tid[top[x]],1)==getv(tid[fa[top[x]][0]],1)) sum--;
        x=fa[top[x]][0];
    }
    sum+=query(tid[y],tid[x],1);
    return sum;
}
void change(int x, int y, int c){
    while(top[x]!=top[y]){
        update(tid[top[x]],tid[x],c,1);
        x=fa[top[x]][0];
    }
    update(tid[y],tid[x],c,1);
}

int main(){
    scanf("%d%d", &n,&m);
    init();
    for(int i=1; i<=n; i++) scanf("%d", &num[i]);
    for(int i=1; i<n; i++){
        int x,y;
        scanf("%d%d", &x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    dfs1(1);
    dfs2(1,1);
    //build(1,n,1);
    //for(int i=1; i<=n; i++) update(tid[i], tid[i], num[i], 1);
    Build(1,n,1);
    for(int i=1; i<=m; i++){
        char op[10];
        scanf("%s", op);
        if(op[0]=='Q'){
            int x,y;
            scanf("%d%d", &x,&y);
            int _lca=lca(x,y);
            int ans = querysum(x,_lca);

            ans += querysum(y,_lca);

            ans-=1;
            printf("%d\n", ans);
        }
        else{
            int x,y,z;
            scanf("%d%d%d", &x,&y,&z);
            int _lca=lca(x,y);
            change(x,_lca,z);
            change(y,_lca,z);
        }
    }
    return 0;
}