2843: 「一本通 4.5 练习 3」染色
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:44
Solved:20
Description
原题来自:SDOI 2011
给定一棵有 $n$ 个节点的无根树和 $m$ 个操作,操作共两类:
C a b c
表示一个染色操作,将节点 $a$ 到节点 $b$ 路径上的所有节点都染上颜色;
Q a b
表示一个询问操作,询问节点 $a$ 到节点 $b$ 路径上的颜色段数量,连续相同颜色的认为是同一段,例如 $112221$ 由 $11$、$222$、$1$ 三段组成。
请你写一个程序依次完成操作。
Input
第一行包括两个整数 $n,m$,表示节点数和操作数;
第二行包含 $n$ 个正整数表示 $n$ 个节点的初始颜色;
接下来若干行包含两个整数 $x$ 和 $y$,表示 $x$ 和 $y$ 之间有一条无向边;
接下来若干行每行描述一个操作。
Output
对于每个询问操作,输出一行询问结果。
Sample Input Copy
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
Sample Output Copy
3
1
2
HINT
对于 $100\%$ 的数据,$N,M \leq 10^5$,所有颜色 $c$ 为整数且在 $[0,10^9]$ 之间。