題目 2469:
信息學奧賽一本通T1563-染色
時間限制: 2s
內存限制: 192MB 提交: 4 解決: 4
題目描述
原題來自：SDOI 2011
給定一棵有 n 個節(jié)點的無根樹和 m 個操作，操作共兩類。
1、將節(jié)點 a 到節(jié)點 b 路徑上的所有節(jié)點都染上顏色；
2、詢問節(jié)點 a 到節(jié)點 b 路徑上的顏色段數(shù)量，連續(xù)相同顏色的認為是同一段，例如 112221 由三段組成：11 、 222、1。
請你寫一個程序依次完成操作。
輸入格式
第一行包括兩個整數(shù) n,m，表示節(jié)點數(shù)和操作數(shù)；
第二行包含 n 個正整數(shù)表示 n 個節(jié)點的初始顏色；
接下來若干行包含兩個整數(shù) x 和 y，表示 x 和 y 之間有一條無向邊；
接下來若干行每行描述一個操作：
1、C a b c 表示這是一個染色操作，把節(jié)點 a 到節(jié)點 b 路徑上所有點（包括 a 和 b）染上顏色；
2、Q a b 表示這是一個詢問操作，把節(jié)點 a 到節(jié)點 b 路徑上（包括 a 和 b）的顏色段數(shù)量。
樣例輸入
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
提示
數(shù)據(jù)范圍與提示：
對于 100% 的數(shù)據(jù)，N,M≤105 ， 所有顏色 C 為整數(shù)且在 [0,109]之間。