给定一棵 n 个结点的无根树,共有 m 个操作,操作分为两种: 1.将结点 a 到结点 b 的路径上的所有点(包括 a 和 b)都染成颜色 c。 2.询问结点 a 到结点 b 的路径上的颜色段数量。 颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成:11、222、1。
输入的第 1 行是用空格隔开的两个整数,分别代表树的结点个数 n 和操作个数 m。 第 2 行有 n 个用空格隔开的整数,第 i 个整数 wi 代表结点 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 路径上的颜色段数量。
对于每次查询操作,输出一行一个整数代表答案。
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%的数据,1 ≤ n,m ≤ 10^5,1 ≤ wi,c ≤ 10^9,1 ≤ a,b,u,v ≤ n,op 一定为 C 或 Q,保证给出的图是一棵树。