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]之间。

#include
      
       #include
       
        #define N 100010using namespace std;int a[N],head[N],fa[N],son[N],dep[N],pos[N],top[N],lco[N*4],rco[N*4],sum[N*4],tag[N*4],n,m,sz;struct node{    int to,pre;};node e[N*2];void add(int i,int x,int y){    e[i].to=y;    e[i].pre=head[x];    head[x]=i;}void dfs1(int x){    son[x]=1;    for(int i=head[x];i;i=e[i].pre){        int v=e[i].to;        if(fa[x]==v) continue;        fa[v]=x;dep[v]=dep[x]+1;        dfs1(v);        son[x]+=son[v];    }}void dfs2(int x,int chain){    ++sz;pos[x]=sz;top[x]=chain;int k=0,maxn=0;    for(int i=head[x];i;i=e[i].pre)        if(fa[x]!=e[i].to&&son[e[i].to]>maxn){            k=e[i].to;maxn=son[e[i].to];        }    if(!k) return;    dfs2(k,chain);    for(int i=head[x];i;i=e[i].pre)        if(fa[x]!=e[i].to&&e[i].to!=k)            dfs2(e[i].to,e[i].to);}void pushup(int k){    lco[k]=lco[k*2];rco[k]=rco[k*2+1];    sum[k]=sum[k*2]+sum[k*2+1];    if(rco[k*2]==lco[k*2+1])sum[k]--;}void pushdown(int k){    if(!tag[k]) return;    tag[k*2]=tag[k*2+1]=tag[k];    lco[k*2]=lco[k*2+1]=tag[k];    rco[k*2]=rco[k*2+1]=tag[k];    sum[k*2]=sum[k*2+1]=1;    tag[k]=0;}void change(int l,int r,int k,int x,int y,int v){    if(l>=x&&r<=y){        tag[k]=lco[k]=rco[k]=v;        sum[k]=1;        return;    }    pushdown(k);    int mid=l+r>>1;    if(x<=mid) change(l,mid,k*2,x,y,v);    if(y>mid) change(mid+1,r,k*2+1,x,y,v);    pushup(k);}int query(int l,int r,int k,int x,int y){    if(l==x&&r==y)return sum[k];    pushdown(k);    int mid=l+r>>1;    if(y<=mid) return query(l,mid,k*2,x,y);    else if(x>mid) return query(mid+1,r,k*2+1,x,y);    else {        int ans=query(l,mid,k*2,x,mid)+query(mid+1,r,k*2+1,mid+1,y);        if(rco[k*2]==lco[k*2+1]) ans--;        return ans;    }}int find(int l,int r,int k,int x){    if(l==r)return lco[k];    pushdown(k);    int mid=l+r>>1;    if(x<=mid) return find(l,mid,k*2,x);    else return find(mid+1,r,k*2+1,x);}void xiugai(int x,int y,int v){    while(top[x]!=top[y]){        if(dep[top[x]]
        
         dep[y]) swap(x,y);    change(1,n,1,pos[x],pos[y],v);}int qiuhe(int x,int y){    int ans=0;    while(top[x]!=top[y]){        if(dep[top[x]]
         
          dep[y]) swap(x,y);    ans+=query(1,n,1,pos[x],pos[y]);    return ans;}int main(){    freopen("jh.in","r",stdin);    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    for(int i=1;i