题目描述

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

1. 将节点 $a$ 到节点 $b$ 路径上的所有节点都染上颜色 $c$；
2. 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 $112221$ 由三段组成：$11$、$222$、$1$。

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

输入格式

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

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

接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，表示 $x$ 和 $y$ 之间有一条无向边；

接下来 $m$ 行，每行描述一个操作：

• C a b c：表示这是一个染色操作，把节点 $a$ 到节点 $b$ 路径上所有点（包括 $a$ 和 $b$）染上颜色 $c$；
• Q a b：表示这是一个询问操作，询问节点 $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

样例解释

树结构（节点上数字为初始颜色）：

      1(2)
     / \
  2(2) 3(1)
  /|\
4 5 6
(2)(1)(1)

括号内为初始颜色。

操作解释：

1. Q 3 5：询问路径 $3 \to 1 \to 2 \to 5$ 上的颜色段。颜色依次为 $1, 2, 2, 1$，段为 $(1), (2,2), (1)$ 共 $3$ 段。
2. C 2 1 1：将路径 $2 \to 1$ 上所有节点染成颜色 $1$。节点 $1$ 和 $2$ 变为颜色 $1$。
3. Q 3 5：路径 $3 \to 1 \to 2 \to 5$ 颜色为 $1, 1, 1, 1$，只有 $1$ 段。
4. C 5 1 2：将路径 $5 \to 2 \to 1$ 染成颜色 $2$。节点 $5,2,1$ 变为颜色 $2$。
5. Q 3 5：路径 $3 \to 1 \to 2 \to 5$ 颜色为 $1, 2, 2, 2$，段为 $(1), (2,2,2)$ 共 $2$ 段。

数据范围

• $N,M \le 10^5$
• 所有颜色 $C$ 为整数且在 $[0,10^9]$ 之间。

时间限制：1000 ms
内存限制：524288 KB

提示

本题是树链剖分的进阶应用，需要维护区间颜色段数量。

基本思路：

1. 对树进行树链剖分，将树上路径转化为若干条重链对应的区间。
2. 用线段树维护每个区间：
   • 区间左端点的颜色 $lc$
   • 区间右端点的颜色 $rc$
   • 区间内颜色段的数量 $cnt$
3. 线段树需要支持区间覆盖（染色）和区间合并查询。

合并操作： 当合并两个相邻区间 $L$ 和 $R$ 时：

• 如果 $L.rc = R.lc$，则 $cnt = L.cnt + R.cnt - 1$（因为中间相邻颜色相同，段数合并时减少一段）；
• 否则 $cnt = L.cnt + R.cnt$。
• 合并后的 $lc = L.lc$，$rc = R.rc$。

路径查询： 对于路径 $(u,v)$，在树链剖分跳链的过程中，我们分别从 $u$ 和 $v$ 向 LCA 跳，记录两段链的信息（注意方向）。最后将两段链的信息合并。因为跳链时顺序可能颠倒，需要分别维护从上到下的链段信息，然后正确合并。

染色操作： 路径覆盖，打懒标记即可。

时间复杂度： $O((n+m) \log^2 n)$。

注意：

• 颜色值范围较大，但颜色段只关心相邻是否相等，可以用整数存储。
• 树是无根的，可以任意指定根（如 $1$）。
• 在跳链查询时，要注意合并的顺序，因为路径是有方向的。通常做法是用两个结构体分别记录从 $u$ 向上跳的信息和从 $v$ 向上跳的信息，最后将这两部分合并。