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

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

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

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

第一行包含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）路径上的颜色段数量。

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

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

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define lch (now<<1)#define rch (now<<1^1)#define MAXN 110000#define MAXT 400010#define MAXE 200010int n,m;int col1[MAXN];int col2[MAXN];struct node {        int lc,rc;        int l,r;        int tot;        int flag;}tree[MAXT];void update(int now){        if (tree[now].l==tree[now].r)tree[now].tot=1;        else        {                tree[now].tot=tree[lch].tot+tree[rch].tot-(tree[lch].rc==tree[rch].lc);                tree[now].lc=tree[lch].lc;                tree[now].rc=tree[rch].rc;        }}void down(int now){        if (tree[now].l==tree[now].r)        {                if (tree[now].flag)                        tree[now].flag=false;                return ;        }        if (tree[now].flag)        {                tree[lch].flag=tree[rch].flag=tree[now].flag;                tree[lch].tot=1;                tree[lch].lc=tree[lch].rc=tree[now].flag;                tree[rch].tot=1;                tree[rch].lc=tree[rch].rc=tree[now].flag;                tree[now].flag=0;        }}void build_tree(int now,int l,int r){        tree[now].l=l;        tree[now].r=r;        tree[now].lc=col2[l];        tree[now].rc=col2[r];        tree[now].flag=0;        if (l==r)        {                tree[now].tot=1;                return ;        }        int mid=(l+r)/2;        build_tree(lch,l,mid);        build_tree(rch,mid+1,r);        update(now);}node comb_seg(node n1,node n2){        node ret;        ret.lc=n1.lc;        ret.rc=n2.rc;        ret.tot=n1.tot+n2.tot-(n1.rc==n2.lc);        return ret;}node turn (node now){        swap(now.lc,now.rc);        return now;}node get_seg(int now,int l,int r){        int i,j,k;        node ret;        bool flip=false;        if (l>r)swap(l,r),flip=true;        down(now);        if (tree[now].l==l&&tree[now].r==r)        {                ret=tree[now];                if (flip)turn(ret);                return ret;        }        int mid=(tree[now].l+tree[now].r)/2;        if (r<=mid)        {                if (flip)return turn(get_seg(lch,l,r));                else return get_seg(lch,l,r);        }        if (mid<l)        {                if (flip)return turn(get_seg(rch,l,r));                else return get_seg(rch,l,r);        }        ret=comb_seg(get_seg(lch,l,mid),get_seg(rch,mid+1,r));        if (flip)return turn(ret);        else return ret;}void set_val(int now,int l,int r,int v){        if (l>r)swap(l,r);        if (tree[now].l==l&&tree[now].r==r)        {                tree[now].tot=1;                tree[now].lc=tree[now].rc=v;                tree[now].flag=v;                return ;        }        down(now);        int mid=(tree[now].l+tree[now].r)/2;        if (r<=mid)        {                set_val(lch,l,r,v);                update(now);                return ;        }        if (mid<l)        {                set_val(rch,l,r,v);                update(now);                return ;        }        set_val(lch,l,mid,v);        set_val(rch,mid+1,r,v);        update(now);}struct Edge{        int np;        Edge *next;}E[MAXE],*V[MAXN];int tope=-1,root;void addedge(int x,int y){        E[++tope].np=y;        E[tope].next=V[x];        V[x]=&E[tope];}int siz[MAXN];int depth[MAXN];int fa[MAXN];int son[MAXN];int dfn[MAXN],cnt=0;int ptr[MAXN];int top[MAXN];int dfs1(int now,int d){        Edge *ne;        int t,mx=0;        depth[now]=d;        siz[now]=1;        son[now]=0;        for (ne=V[now];ne;ne=ne->next)        {                if(ne->np==fa[now])continue;                fa[ne->np]=now;                t=dfs1(ne->np,d+1);                if (t>mx)                {                        mx=t;                        son[now]=ne->np;                }                siz[now]+=t;        }        return siz[now];}void dfs2(int now,int tp){        Edge *ne;        dfn[now]=++cnt;        ptr[cnt]=now;        top[now]=tp;        if (son[now])                dfs2(son[now],tp);        for (ne=V[now];ne;ne=ne->next)        {                if (ne->np==fa[now]||ne->np==son[now])continue;                dfs2(ne->np,ne->np);        }}int jump[MAXN][21];void init_lca(){        int i,j;        for (i=1;i<=n;i++)        {                jump[i][0]=fa[i];        }        for (j=1;j<20;j++)        {                for (i=1;i<=n;i++)                {                        jump[i][j]=jump[jump[i][j-1]][j-1];                }        }}int swim(int x,int d){        int i=0,ret=x;        while (d)        {                if (d&1)                {                        ret=jump[ret][i];                }                i++;                d>>=1;        }        return ret;}int get_lca(int x,int y){        if (depth[x]>depth[y])                x=swim(x,depth[x]-depth[y]);        else                 y=swim(y,depth[y]-depth[x]);        if (x==y)return x;        int i;        for (i=19;i>=0;i--)        {                if (jump[x][i]!=jump[y][i])                {                        x=jump[x][i];                        y=jump[y][i];                }        }        return fa[x];}int query(int x,int y){        int lca;        lca=get_lca(x,y);        node n1,n2;        n1.tot=0;        n1.rc=0;        n1.lc=0;        n1.l=dfn[x];        n1.r=dfn[x];        n2=n1;        while (true)        {                if (top[x]==top[lca])                {                        n1=comb_seg(n1,get_seg(1,dfn[x],dfn[lca]));                        break;                }                n1=comb_seg(n1,get_seg(1,dfn[x],dfn[top[x]]));                x=fa[top[x]];        }        if (lca==y)return n1.tot;        int d=depth[y]-depth[lca]-1;;        int t=swim(y,d);        while (true)        {                if (top[y]==top[t])                {                        n2=comb_seg(get_seg(1,dfn[t],dfn[y]),n2);                        break;                }                n2=comb_seg(get_seg(1,dfn[top[y]],dfn[y]),n2);                y=fa[top[y]];        }        n1=comb_seg(n1,n2);        return n1.tot;}void paint_color(int x,int y,int z){        int lca;        lca=get_lca(x,y);        while (true)        {                if (top[x]==top[lca])                {                        set_val(1,dfn[x],dfn[lca],z);                        break;                }                set_val(1,dfn[x],dfn[top[x]],z);                x=fa[top[x]];        }        if (y==lca)return ;        int d=depth[y]-depth[lca]-1;;        int t=swim(y,d);        while (true)        {                if (top[y]==top[t])                {                        set_val(1,dfn[y],dfn[t],z);                        break;                }                set_val(1,dfn[y],dfn[top[y]],z);                y=fa[top[y]];        }}int main(){        //freopen("input.txt","r",stdin);        int i,j,k,x,y,z;        scanf("%d%d",&n,&m);        for (i=0;i<n;i++)        {                scanf("%d",col1+i+1);        }        for (i=1;i<n;i++)        {                scanf("%d%d",&x,&y);                addedge(x,y);                addedge(y,x);        }        root=1;        fa[root]=root;        dfs1(root,0);        dfs2(root,root);        init_lca();        for (i=1;i<=n;i++)                col2[dfn[i]]=col1[i];        build_tree(1,1,cnt);        scanf("\n");        char opt;        while (m--)        {                scanf("%c",&opt);                if (opt==‘Q‘)                {                        scanf("%d%d\n",&x,&y);                        printf("%d\n",query(x,y));                }else                {                        scanf("%d%d%d\n",&x,&y,&z);                        paint_color(x,y,z);                }        }}