Migrated from Lutece 2750 树上颜色段

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作。

对于这 $m$ 个操作，分为 $2$ 种：

• 操作 1： 将节点 $a$ 到节点 $b$ 路径上所有点都染成颜色 $c$
• 操作 2： 询问树上节点 $a$ 到节点 $b$ 简单路径上的颜色段数量（连续相同颜色被认为是同一段）

如 $2332221$ 由 $4$ 段组成：$2$、$33$、$222$ 和 $1$。

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

Input

输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 $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$ 路径上的颜色段数量。

Output

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

Samples

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

Constraints

$1\le n,m \leq 10^5$ $0\le w_i, c \leq 10^9$ $1\le a, b, u, v \leq n$ 数据保证给出的是树

Resources

2022 UESTC ICPC Training for Data Structures