问题标题: 酷町堂：6980

题目链接： 酷町堂：6980

6980   染色

经验值：2800 时间限制：1000毫秒 内存限制：512MB

题目描述 De**ion

给定一棵有 nn 个节点的无根树和 mm 个操作，操作共两类。

1. 将节点 aa 到节点 bb 路径上的所有节点都染上颜色；

2. 询问节点 aa 到节点 bb 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 112221 由三段组成：11 、 222、1。

请你写一个程序依次完成操作。

输入描述 Input De**ion

第一行包括两个整数 n,mn,m，表示节点数和操作数；

第二行包含 nn 个正整数表示 nn 个节点的初始颜色；

接下来若干行包含两个整数 xx 和 yy，表示 xx 和 yy 之间有一条无向边；

接下来若干行每行描述一个操作：

• C a b c 表示这是一个染色操作，把节点 aa 到节点 bb 路径上所有点（包括 aa 和 bb）染上颜色；

• Q a b 表示这是一个询问操作，把节点 aa 到节点 bb 路径上（包括 aa 和 bb）的颜色段数量。

输出描述 Output De**ion

对于每个询问操作，输出一行询问结果。

样例输入 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

数据范围及提示 Data Size & Hint

对于 100\%100% 的数据，N,M \le 10^5N,M≤105， 所有颜色 CC 为整数且在 [0,10^9][0,109] 之间。

 

我的代码只得了50分，求AC代码，谢谢大神们！