给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
给定一棵有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]之间。
树链剖分练习。
1.每次查询时记得跳上去时，要把两个端点是否相等计算进去。color[num[fa[top[x]]]]==color[num[top[x]]]记得判断，这里用单点查询即可。
（这里不会出现错误，有人会想：fa[top[x]]会不会跳到了这两个点的路径外？不会，因为当dep[top[x]]<dep[top[x]时交换x,y所以当x已经在最上面的区间时，他就不会动了，只有y会向上跳）
2.每次查询时query(l,mid) query(mid+1,r)时也要判断rc[x*2]==lc[x*2+1]（查询时）当且仅当a<=mid<b时要判断；（a,b是要查询的区间），因为如果这两个端点不在查询的区间里，那么也就没有必要判断了。
3.tag要先变成-1，颜色可能为0
4.pushdown是把下面节点的信息修改，不是仅仅修改他的tag。（不清楚）
一组数据：
7 3
1 1 1 1 1 1 1
1 2 1 3
2 4 2 5
3 6 3 7
C 6 3 2
C 4 7 1
Q 6 7
这组数据说明了第二条
原文：http://www.cnblogs.com/19992147orz/p/6250350.html