A5463. 「一本通 4.5 练习 3」染色
编程题
提高+/省选-
知识点
题目描述
**原题来自：SDOI 2011**
给定一棵有 $n$ 个节点的无根树和 $m$ 个操作，操作共两类。
1. 将节点 $a$ 到节点 $b$ 路径上的所有节点都染上颜色；
2. 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量，连续相同颜色的认为是同一段，例如
请你写一个程序依次完成操作。
给定一棵有 $n$ 个节点的无根树和 $m$ 个操作，操作共两类。
1. 将节点 $a$ 到节点 $b$ 路径上的所有节点都染上颜色；
2. 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量，连续相同颜色的认为是同一段，例如
112221 由三段组成：11 、 222、1。请你写一个程序依次完成操作。
输入格式
第一行包括两个整数 $n,m$，表示节点数和操作数；
第二行包含 $n$ 个正整数表示 $n$ 个节点的初始颜色；
接下来若干行包含两个整数 $x$ 和 $y$，表示 $x$ 和 $y$ 之间有一条无向边；
接下来若干行每行描述一个操作：
+
+
第二行包含 $n$ 个正整数表示 $n$ 个节点的初始颜色；
接下来若干行包含两个整数 $x$ 和 $y$，表示 $x$ 和 $y$ 之间有一条无向边；
接下来若干行每行描述一个操作：
+
C a b c 表示这是一个染色操作，把节点 $a$ 到节点 $b$ 路径上所有点（包括 $a$ 和 $b$）染上颜色；+
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
说明/提示
对于 $100\%$ 的数据，$N,M \le 10^5$， 所有颜色 $C$ 为整数且在 $[0,10^9]$ 之间。