7078: 「一本通 4.5 练习 3」染色
[Creator : ]
Description
原题来自：SDOI 2011
给定一棵有 n 个节点的无根树和 m 个操作，操作共两类。
给定一棵有 n 个节点的无根树和 m 个操作，操作共两类。
-
将节点 a 到节点 b 路径上的所有节点都染上颜色；
-
询问节点 a 到节点 b 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 112221 由三段组成：11 、 222、1。
Input
第一行包括两个整数 n,m，表示节点数和操作数；
第二行包含 n 个正整数表示 n 个节点的初始颜色；
接下来若干行包含两个整数 x 和 y，表示 x 和 y 之间有一条无向边；
接下来若干行每行描述一个操作：
第二行包含 n 个正整数表示 n 个节点的初始颜色；
接下来若干行包含两个整数 x 和 y，表示 x 和 y 之间有一条无向边；
接下来若干行每行描述一个操作：
-
C a b c 表示这是一个染色操作，把节点 a 到节点 b 路径上所有点（包括 a 和 b）染上颜色；
-
Q a b 表示这是一个询问操作，把节点 a 到节点 b 路径上（包括 a 和 b）的颜色段数量。
Output
对于每个询问操作，输出一行询问结果。
Constraints
对于 $100\%$ 的数据，$N,M \le 10^5$， 所有颜色 $C$ 为整数且在 $[0,10^9]$ 之间。
Sample 1 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 1 Output
3
1
2