题目描述
原题来自：SDOI 2011
给定一棵有
n
n 个节点的无根树和
m
m 个操作，操作共两类。
将节点
a
a 到节点
b
b 路径上的所有节点都染上颜色；
询问节点
a
a 到节点
b
b 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 112221 由三段组成：11 、 222、1。
请你写一个程序依次完成操作。
输入
第一行包括两个整数
n,m
n,m，表示节点数和操作数；
第二行包含
n
n 个正整数表示
n
n 个节点的初始颜色；
接下来若干行包含两个整数
x
x 和
y
y，表示
x
x 和
y
y 之间有一条无向边；
接下来若干行每行描述一个操作：
C a b c 表示这是一个染色操作，把节点
a
a 到节点
b
b 路径上所有点（包括
a
a 和
b
b）染上颜色；
Q a b 表示这是一个询问操作，把节点
a
a 到节点
b
b 路径上（包括
a
a 和
b
b）的颜色段数量。
输出
对于每个询问操作，输出一行询问结果。
样例输入
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
样例输出
3
1
2
提示
数据范围与提示
对于
100\%
100% 的数据，
N,M \le 10^5
N,M≤105， 所有颜色
C
C 为整数且在
[0,10^9]
[0,109] 之间。
来源/分类
ybttg 树链剖分