#P2486. [SDOI2011] 染色

    ID: 57 远端评测题 1000ms 125MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>2011线段树各省省选山东动态树树链剖分,树剖

[SDOI2011] 染色

题目描述

给定一棵 nn 个节点的无根树,共有 mm 个操作,操作分为两种:

  1. 将节点 aa 到节点 bb 的路径上的所有点(包括 aabb)都染成颜色 cc
  2. 询问节点 aa 到节点 bb 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成:112221

输入格式

输入的第一行是用空格隔开的两个整数,分别代表树的节点个数 nn 和操作个数 mm

第二行有 nn 个用空格隔开的整数,第 ii 个整数 wiw_i 代表结点 ii 的初始颜色。

33 到第 (n+1)(n + 1) 行,每行两个用空格隔开的整数 u,vu, v,代表树上存在一条连结节点 uu 和节点 vv 的边。

(n+2)(n + 2) 到第 (n+m+1)(n + m + 1) 行,每行描述一个操作,其格式为:

每行首先有一个字符 opop,代表本次操作的类型。

  • opopC,则代表本次操作是一次染色操作,在一个空格后有三个用空格隔开的整数 a,b,ca, b, c,代表将 aabb 的路径上所有点都染成颜色 cc
  • opopQ,则代表本次操作是一次查询操作,在一个空格后有两个用空格隔开的整数 a,ba, b,表示查询 aabb 路径上的颜色段数量。

输出格式

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

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%100\% 的数据,1n,m1051 \leq n, m \leq 10^51wi,c1091 \leq w_i, c \leq 10^91a,b,u,vn1 \leq a, b, u, v \leq nopop 一定为 CQ,保证给出的图是一棵树。

除原数据外,还存在一组不计分的 hack 数据。