[SDOI2011]染色

时间限制:20s      空间限制:512MB

题目描述

给定一棵有n个节点的无根树和m个操作,操作有2类:

1、将节点a到节点b路径上所有点都染成颜色c

2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“1122213段组成:“11、“222和“1

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


输入格式

第一行包含2个整数nm,分别表示节点数和操作数;

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

下面 行每行包含两个整数xy,表示xy之间有一条无向边。

下面 行每行描述一个操作:

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

“Q a b”表示这是一个询问操作,询问节点a到节点b(包括ab)路径上的颜色段数量。


输出格式

对于每个询问操作,输出一行答案。


样例输入

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

提示

数N<=10^5,操作数M<=10^5,所有的颜色C为整数且在[0, 10^9]之间。


题目来源

第一轮day1