[SDOI2011] 染色

题目描述

给定一棵 $n$ 个节点的无根树,共有 $m$ 个操作,操作分为两种: 1. 将节点 $a$ 到节点 $b$ 的路径上的所有点(包括 $a$ 和 $b$)都染成颜色 $c$。 2. 询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量。 颜色段的定义是极长的连续相同颜色被认为是一段。例如 `112221` 由三段组成:`11`、`222`、`1`。

输入输出格式

输入格式


输入的第一行是用空格隔开的两个整数,分别代表树的节点个数 $n$ 和操作个数 $m$。 第二行有 $n$ 个用空格隔开的整数,第 $i$ 个整数 $w_i$ 代表结点 $i$ 的初始颜色。 第 $3$ 到第 $(n + 1)$ 行,每行两个用空格隔开的整数 $u, v$,代表树上存在一条连结节点 $u$ 和节点 $v$ 的边。 第 $(n + 2)$ 到第 $(n + m + 1)$ 行,每行描述一个操作,其格式为: 每行首先有一个字符 $op$,代表本次操作的类型。 - 若 $op$ 为 `C`,则代表本次操作是一次染色操作,在一个空格后有三个用空格隔开的整数 $a, b, c$,代表将 $a$ 到 $b$ 的路径上所有点都染成颜色 $c$。 - 若 $op$ 为 `Q`,则代表本次操作是一次查询操作,在一个空格后有两个用空格隔开的整数 $a, b$,表示查询 $a$ 到 $b$ 路径上的颜色段数量。

输出格式


对于每次查询操作,输出一行一个整数代表答案。

输入输出样例

输入样例 #1

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

输出样例 #1

3
1
2

说明

#### 数据规模与约定 对于 $100\%$ 的数据,$1 \leq n, m \leq 10^5$,$1 \leq w_i, c \leq 10^9$,$1 \leq a, b, u, v \leq n$,$op$ 一定为 `C` 或 `Q`,保证给出的图是一棵树。 除原数据外,还存在一组不计分的 hack 数据。