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]之间。
题解
这个一眼就能看出来树剖吧。。
树剖的线段树的话维护一下这一段最左边的颜色，最右边的颜色，以及本身的颜色（不是纯色的话就为-1），打个lazy搞一下。。
修改我就不废话了大家都会吧。。
查询时x和y往上跳的时候分别维护两个值lasx和lasy，表示x，y当前查询到的最后一段上最上面那段的颜色。线段树问的时候维护两个值fir和tmp，表示当前查询这一段最下面的颜色和最上面的颜色。出来之后看一看fir和跳的这个las是不是相等，相等的话答案就要-1。之后las继承为tmp
如果你分不清我上面说的las的话请你看一看树剖跳轻重链的过程。那里会把lasx和lasy交换一下的
线段树查询的时候有一个小小的坑点。。上面说要维护一下这个段最左边和最右边的颜色，就是因为怕分开查询的时候中间连接的地方其实是一段，然后那里也是需要判一下的。。
实在听不下去我口胡的可以看一看代码。。我觉得可看性还是挺强的
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{int x,y,next;
}a[211000];int len,last[111000];
void ins(int x,int y)
{len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;
}
int fa[111000],dep[111000],tot[111000],son[111000],n,m;
void pre_tree_node(int x)
{son[x]=0;tot[x]=1;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y!=fa[x]){fa[y]=x;dep[y]=dep[x]+1;pre_tree_node(y);if(tot[son[x]]<tot[y])son[x]=y;tot[x]+=tot[y];}}
}
int ys[111000],top[111000],z;
void pre_tree_edge(int x,int tp)
{ys[x]=++z;top[x]=tp;if(son[x]!=0)pre_tree_edge(son[x],tp);for(int k=last[x];k;k=a[k].next)if(son[x]!=a[k].y && fa[x]!=a[k].y)pre_tree_edge(a[k].y,a[k].y);
}
struct trnode
{int lc,rc,l,r,c;int lef,rig;bool lazy;
}tr[410000];int trlen;
void bt(int l,int r)
{int now=++trlen;tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;tr[now].c=tr[now].lef=tr[now].rig=0;tr[now].lazy=false;if(l<r){int mid=(l+r)/2;tr[now].lc=trlen+1;bt(l,mid);tr[now].rc=trlen+1;bt(mid+1,r);}
}
void upd(int x)
{int lc=tr[x].lc,rc=tr[x].rc;tr[lc].lazy=tr[rc].lazy=true;tr[lc].c=tr[rc].c=tr[x].c;tr[lc].lef=tr[lc].rig=tr[rc].lef=tr[rc].rig=tr[x].c;tr[x].lazy=false;
}
int lasx,lasy,fir,tmp,col[111000];
void change(int now,int l,int r,int c)
{if(tr[now].l==l && tr[now].r==r){tr[now].c=tr[now].lef=tr[now].rig=c;tr[now].lazy=true;return ;}int lc=tr[now].lc,rc=tr[now].rc;int mid=(tr[now].l+tr[now].r)/2;if(tr[now].lazy)upd(now);if(r<=mid)change(lc,l,r,c);else if(mid+1<=l)change(rc,l,r,c);else change(lc,l,mid,c),change(rc,mid+1,r,c);if(tr[lc].c==tr[rc].c)tr[now].c=tr[lc].c;else tr[now].c=-1;tr[now].lef=tr[lc].lef;tr[now].rig=tr[rc].rig;
}
int findsum(int now,int l,int r,int lef,int rig)
{if(tr[now].c!=-1){if(r>=rig)fir=tr[now].c;//问到了最下面的那个 if(l<=lef)tmp=tr[now].c;//最上面的那个 return 1;}int lc=tr[now].lc,rc=tr[now].rc;int mid=(tr[now].l+tr[now].r)/2;if(tr[now].lazy)upd(now);if(r<=mid)return findsum(lc,l,r,lef,rig);else if(mid+1<=l)return findsum(rc,l,r,lef,rig);else {int retx=findsum(lc,l,mid,lef,rig),rety=findsum(rc,mid+1,r,lef,rig);if(tr[lc].rig==tr[rc].lef)return retx+rety-1;//中间其实是一段的情况 return retx+rety;}
}
void chmul(int x,int y,int c)
{int tx=top[x],ty=top[y];while(tx!=ty){if(dep[ty]<dep[tx])swap(x,y),swap(tx,ty);change(1,ys[ty],ys[y],c);y=fa[ty];ty=top[y];}if(x==y){change(1,ys[x],ys[x],c);return ;}else{if(dep[x]>dep[y])swap(x,y);change(1,ys[x],ys[y],c);return ; }
}
int sol(int x,int y)
{int tx=top[x],ty=top[y],ans=0;lasx=lasy=-999999999;while(tx!=ty){if(dep[ty]<dep[tx])swap(x,y),swap(tx,ty),swap(lasx,lasy);ans+=findsum(1,ys[ty],ys[y],ys[ty],ys[y]);if(fir==lasy)ans--;lasy=tmp;y=fa[ty];ty=top[y];}if(x==y){ans+=findsum(1,ys[x],ys[x],ys[x],ys[x]);if(fir==lasx)ans--;if(fir==lasy)ans--;return ans;}else{if(dep[x]>dep[y])swap(x,y),swap(lasx,lasy);ans+=findsum(1,ys[x],ys[y],ys[x],ys[y]);//x在上 y在下 if(fir==lasy)ans--;if(tmp==lasx)ans--;return ans;}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&col[i]);len=0;memset(last,0,sizeof(last));for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);ins(x,y);ins(y,x);}fa[1]=0;dep[1]=0;pre_tree_node(1);z=0;pre_tree_edge(1,1);trlen=0;bt(1,z);for(int i=1;i<=n;i++)change(1,ys[i],ys[i],col[i]);while(m--){char ss[10];int x,y,c;scanf("%s%d%d",ss+1,&x,&y);if(ss[1]=='C'){scanf("%d",&c);chmul(x,y,c);}else printf("%d\n",sol(x,y));}return 0;
}