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
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
1
2
HINT
数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
Source
第一轮day1
树链剖分~
对于每一个区间我们记录c[k].l c[k].r c[k].lc c[k].rc c[k].num，分别表示左右位置，最左面节点的颜色，最右面节点的颜色以及区间内段数。所以每次合并时判断两区间相交处是否颜色相同即可。剩余的部分就和普通的树链剖分一样了~
注意dep[1]要设为1，防止lca出错。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;int n,m,x,y,z,a[100001],fi[100001],w[200001],ne[200001],cnt,dep[100001],son[100001],id[100001],siz[100001],fa[100001][17],top[100001];
char s[2];struct node{int l,r,lc,rc,num,tag;
}c[100001<<2];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,int v)
{w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;w[++cnt]=u;ne[cnt]=fi[v];fi[v]=cnt;
}void dfs1(int u)
{for(int i=1;i<=16;i++) fa[u][i]=fa[fa[u][i-1]][i-1];siz[u]=1;for(int i=fi[u];i;i=ne[i])if(w[i]!=fa[u][0]){fa[w[i]][0]=u;dep[w[i]]=dep[u]+1;dfs1(w[i]);siz[u]+=siz[w[i]];if(!son[u] || siz[son[u]]<siz[w[i]]) son[u]=w[i];}
}void dfs2(int u,int la)
{id[u]=++cnt;top[u]=la;if(son[u]) dfs2(son[u],la);for(int i=fi[u];i;i=ne[i])if(w[i]!=fa[u][0] && w[i]!=son[u]) dfs2(w[i],w[i]);
}int lca(int u,int v)
{if(dep[u]<dep[v]) swap(u,v);for(int i=16;~i;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];if(u==v) return u;for(int i=16;~i;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];return fa[u][0];
}void update(int k)
{int l=k<<1,r=k<<1|1;c[k].lc=c[l].lc;c[k].rc=c[r].rc;c[k].num=c[l].num+c[r].num;if(c[l].rc==c[r].lc) c[k].num--;
}void pushdown(int k)
{int l=c[k].l,r=c[k].r;if(c[k].tag==-1 || l==r) return;c[k<<1].tag=c[k<<1|1].tag=c[k].tag;c[k<<1].lc=c[k<<1|1].lc=c[k<<1].rc=c[k<<1|1].rc=c[k].tag;c[k].tag=-1;c[k<<1].num=c[k<<1|1].num=1;
}void build(int l,int r,int k)
{c[k].l=l;c[k].r=r;c[k].tag=-1;c[k].num=1;if(l==r) return;int mid=l+r>>1;build(l,mid,k<<1);build(mid+1,r,k<<1|1);
}void chan(int k,int u,int v,int col)
{pushdown(k);int l=c[k].l,r=c[k].r,mid=l+r>>1;if(l>=u && r<=v){c[k].lc=c[k].rc=c[k].tag=col;c[k].num=1;return;}if(mid>=u) chan(k<<1,u,v,col);if(mid<v) chan(k<<1|1,u,v,col);update(k);
}int getcol(int k,int u)
{pushdown(k);int l=c[k].l,r=c[k].r,mid=l+r>>1;if(l==r) return c[k].lc;if(mid>=u) return getcol(k<<1,u);return getcol(k<<1|1,u);
}void chancol(int u,int v,int col)
{int x=top[u],y=top[v];while(x!=y){chan(1,id[x],id[u],col);u=fa[x][0];x=top[u];}chan(1,id[v],id[u],col);
}int cal(int k,int u,int v)
{pushdown(k);int l=c[k].l,r=c[k].r,mid=l+r>>1,now;if(l>=u && r<=v) return c[k].num;if(mid>=v) return cal(k<<1,u,v);if(mid<u) return cal(k<<1|1,u,v);now=cal(k<<1,u,v)+cal(k<<1|1,u,v);if(c[k<<1].rc==c[k<<1|1].lc) now--;return now;
}int getnum(int u,int v)
{int x=top[u],y=top[v],now=0;while(x!=y){now+=cal(1,id[x],id[u]);if(getcol(1,id[x])==getcol(1,id[fa[x][0]])) now--;u=fa[x][0];x=top[u];}return now+cal(1,id[v],id[u]);
}int main()
{n=read();m=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<n;i++) x=read(),y=read(),add(x,y);cnt=0;dep[1]=1;dfs1(1);dfs2(1,1);build(1,n,1);for(int i=1;i<=n;i++) chan(1,id[i],id[i],a[i]);while(m--){scanf("%s",s);x=read();y=read();if(s[0]=='C'){int k=lca(x,y);z=read();chancol(x,k,z);chancol(y,k,z);}else{int k=lca(x,y);printf("%d\n",getnum(x,k)+getnum(y,k)-1);}}return 0;
}