#10141. 「一本通 4.5 练习 3」染色

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

原题来自:SDOI 2011

给定一棵有 n 个节点的无根树和 m 个操作,操作共两类。

  1. 将节点 a 到节点 b 路径上的所有节点都染上颜色;

  2. 询问节点 a 到节点 b 路径上的颜色段数量,连续相同颜色的认为是同一段,例如 112221 由三段组成:112221

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

输入格式

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

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

接下来若干行包含两个整数 x y ,表示 x y 之间有一条无向边;

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

  • C a b c 表示这是一个染色操作,把节点 a 到节点 b 路径上所有点(包括 a b )染上颜色;

  • Q a b 表示这是一个询问操作,把节点 a 到节点 b 路径上(包括 a 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\% 的数据, N,M \le 10^5 , 所有颜色 C 为整数且在 [0,10^9] 之间。