#P2486. [SDOI2011] 染色
[SDOI2011] 染色
题目描述
给定一棵 个节点的无根树,共有 个操作,操作分为两种:
- 将节点 到节点 的路径上的所有点(包括 和 )都染成颜色 。
- 询问节点 到节点 的路径上的颜色段数量。
颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221
由三段组成:11
、222
、1
。
输入格式
输入的第一行是用空格隔开的两个整数,分别代表树的节点个数 和操作个数 。
第二行有 个用空格隔开的整数,第 个整数 代表结点 的初始颜色。
第 到第 行,每行两个用空格隔开的整数 ,代表树上存在一条连结节点 和节点 的边。
第 到第 行,每行描述一个操作,其格式为:
每行首先有一个字符 ,代表本次操作的类型。
- 若 为
C
,则代表本次操作是一次染色操作,在一个空格后有三个用空格隔开的整数 ,代表将 到 的路径上所有点都染成颜色 。 - 若 为
Q
,则代表本次操作是一次查询操作,在一个空格后有两个用空格隔开的整数 ,表示查询 到 路径上的颜色段数量。
输出格式
对于每次查询操作,输出一行一个整数代表答案。
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
提示
数据规模与约定
对于 的数据,,,, 一定为 C
或 Q
,保证给出的图是一棵树。
除原数据外,还存在一组不计分的 hack 数据。