【例題】
[SDOI2011]染色（注：數據范圍木有交代，應為：點數N<=10
5，操作數M<=10
5，所有的顏色C為整數且在[0, 10
9]之間。
一、樹的路徑剖分當中點權型（點上有權值而邊上木有）的處理辦法：
（1）找重鏈建線段樹的時候，w0中存儲tot+1個數，為該重鏈自上而下的各點的權值（例題中為顏色）；
（2）除了父邊是輕邊的葉結點之外，樹中的每個結點都
屬于且僅屬于一條重鏈（根據定義得到），所以，設目前待查路徑的兩個點（也就是路徑的兩端點）為a0和b0，其LCA設為LCA0，則a0上溯到LCA0的時候，先判定a0是不是一個父邊是輕邊的葉結點，如果是，就對它單獨處理，并跳到a0的父結點處開始循環上溯，否則從a0開始循環上溯。上溯時，若UP[a0]木有超越LCA0則上溯到UP[a0]否則上溯到LCA0，找到a0和上溯到的點的ord，再在線段樹中處理，處理完后，跳到a0的父結點處（這里一定要判定是不是根結點），如此循環，直到
超越（等于都不行）LCA0為止（如果LCA0是根，則上溯到根結點后直接強退）。對于b0類似處理即可；
（3）改值的時候，對于父邊是輕邊的葉結點直接改，對于其它結點在其所在重鏈對應的線段樹中改；
二、路徑的銜接問題的處理辦法：
例題中由于要統計顏色段數，涉及到各重鏈之間（包括LCA0附近）的銜接問題，這個問題在點權型和邊權型樹中的處理辦法不同。
下面照樣設目前待查路徑的兩個點（也就是路徑的兩端點）為a0和b0，其LCA設為LCA0。
（1）對于點權型樹：
先考慮a0上溯到LCA0中的情況。在此過程中需要設置“最新點”（準確來說是最新點的權值，即顏色）x0，一開始給x0賦一個不可能存在的值（比如-1、INF等）。首先，如果a0是一個父邊是輕邊的葉結點，則特判過程中需要先將最新點設為a0（的權值），然后在上溯的時候，不斷將最新點改為UP[a0]，每次跳到父結點的時候比較跳到的點與最新點之間的顏色是否相同來進行銜接。對于b0上溯到LCA0的情況類似。不過還有一個地方，就是LCA0附近的銜接，這個在點權型樹的處理辦法是：先將“a0->LCA0”與“B0->LCA0"當成兩條鏈（顯然都包括LCA0），分別處理后，將這兩條鏈銜接起來，由于它們都包括LCA0，銜接處顏色必定相等，故直接減1即可（注意這只是對于本題而言，對于其它題目還是那句話“具體情況具體分析”）
（2）對于邊權型樹：
需要設置的是“最新邊”（一開始最新邊都是不存在的）。上溯過程中存在輕重邊之分，對于輕邊，直接將其與最新邊銜接再將最新邊改為這條邊即可，對于重鏈，將其最后一條邊（注意在線段樹中是最右的，可在過程中記錄）與最新邊銜接，再將最新邊改為這條重鏈的第一條邊（線段樹中最左的，同樣可在過程中記錄）即可。對于“a0->LCA0”與“B0->LCA0"的最右的邊的銜接問題，直接比較即可。
三、一些易疵點和細節問題（新發現的，補充，見代碼中標Attention的地方）：
（1）對于prepare的第4步，深搜的時候，不要把邊的編號（st[i]）與點的編號（i、j）搞混了，回溯的條件應是st[i]==i而不是j==i；
（2）求LCA的時候一定不要忘了“b<a"的情況（要交換），另外LCA可以作為一個函數來搞，省得每個操作都寫；
（3）上溯的時候，對于點權型，不要忘了初始的特判、循環終止條件（超越LCA0）以及跳到父結點時對根結點的處理；
（4）其實，各個操作的上溯過程是可以寫成專門的函數的（當然本沙茶在本例題中木有這樣做）；
（5）維護線段樹中記錄的信息的時候，別搞疵了（本沙茶一開始在opr0中忘了維護lc和rc……）；
（6）線段樹下放標記的時候一定要判斷有木有標記；
（7）關于LCA的求法，NZK神犇（Orz?。。。┍硎居胁恍枰柚鶵MQ或者倍增，直接求的，關鍵是本沙茶還木有搞懂；
（8）調試技巧是很重要的，可以省去大量的讀程序、對拍的時間，甚至可能不用對拍（不過本沙茶太若了還不能實現這一點）；
代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 100001, MAXS = 20, INF = ~0U >> 2;
struct edge {
int a, b, pre, next;
bool Z;
} E0[MAXN << 2], E[MAXN << 2];
struct node {
int lc, rc, seg, lch, rch, mr;
} T[MAXN << 2];
int n, m0, m, N, w[MAXN], Q[MAXN], FA[MAXN], DEP[MAXN], SZ[MAXN], UP[MAXN], ord[MAXN], w0[MAXN], tot[MAXN], root[MAXN];
int stk[MAXN], st[MAXN], A[MAXN << 1], FF[MAXN], A0[MAXN << 1][MAXS], LOG[MAXN << 1], l0, r0, x0, _x1, res;
bool vst[MAXN];
void init_d()
{
re(i, n) E0[i].pre = E0[i].next = E[i].pre = E[i].next = i;
m = m0 = n;
}
void add_edge0(int a, int b)
{
E0[m0].a = a; E0[m0].b = b; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
E0[m0].a = b; E0[m0].b = a; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void add_edge(int a, int b)
{
E[m].a = a; E[m].b = b; E[m].Z = 0; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
int mkt(int l, int r)
{
int No = ++N; T[N].lc = w0[l]; T[N].rc = w0[r]; T[N].mr = INF;
if (l == r) {T[N].seg = 1; T[N].lch = T[N].rch = 0;} else {
int mid = l + r >> 1, l_r = mkt(l, mid), r_r = mkt(mid + 1, r);
T[No].seg = T[T[No].lch = l_r].seg + T[T[No].rch = r_r].seg;
if (w0[mid] == w0[mid + 1]) T[No].seg--;
}
return No;
}
void prepare()
{
N = 0; re(i, n) vst[i] = 0; Q[0] = 0; FA[0] = -1; DEP[0] = 0; vst[0] = 1;
int i, j, x, x0, maxsz, n0, tp;
for (int front=0, rear=0; front<=rear; front++) {
i = Q[front];
for (int p=E0[i].next; p != i; p=E0[p].next) {
j = E0[p].b;
if (!vst[j]) {vst[j] = 1; Q[++rear] = j; FA[j] = m; DEP[j] = DEP[i] + 1; add_edge(i, j);}
}
}
rre(i0, n) {
i = Q[i0]; SZ[i] = 1; maxsz = -INF;
for (int p=E[i].next; p != i; p=E[p].next) {
j = E[p].b; SZ[i] += SZ[j];
if (SZ[j] > maxsz) {maxsz = SZ[j]; x = p;}
}
if (SZ[i] > 1) E[x].Z = 1;
}
UP[0] = ord[0] = 0;
re2(i0, 1, n) {
i = Q[i0]; int p = FA[i];
if (E[p].Z) {UP[i] = UP[E[p].a]; ord[i] = ord[E[p].a] + 1;} else {UP[i] = i; ord[i] = 0;}
if (SZ[i] == 1 && E[p].Z) {
n0 = ord[i]; j = UP[i];
for (int k=i; k!=j; k=E[FA[k]].a) {tot[k] = ord[i] + 1; w0[n0--] = w[k];} tot[j] = ord[i] + 1; w0[0] = w[j];
root[j] = mkt(0, ord[i]); for (int k=i; k!=j; k=E[FA[k]].a) root[k] = root[j];
}
}
stk[tp = 0] = 0; A[0] = 0; n0 = 1; re(i, n) {st[i] = E[i].next; FF[i] = -1;} FF[0] = 0;
while (tp >= 0) {
i = stk[tp]; j = E[st[i]].b;
if (st[i] == i) { //Attention
if (tp) A[n0++] = stk[tp - 1]; tp--;
} else {
A[n0++] = j; stk[++tp] = j; st[i] = E[st[i]].next;
if (FF[j] == -1) FF[j] = n0 - 1;
}
}
rre(i, n0) {
A0[i][0] = A[i]; x = 1;
re2(j, 1, MAXS) {
x0 = x << 1;
if (i + x0 <= n0) {A0[i][j] = DEP[A0[i][j - 1]] <= DEP[A0[i + x][j - 1]] ? A0[i][j - 1] : A0[i + x][j - 1]; x = x0;} else break;
}
}
x = 1;
re(i, MAXS) {
x0 = x << 1;
if (x0 <= n0) {re2(j, x, x0) LOG[j] = i; x = x0;} else {re2(j, x, n0) LOG[j] = i; break;}
}
}
int LCA(int a1, int b1)
{
int a = FF[a1], b = FF[b1], tmp;
if (a > b) {tmp = a; a = b; b = tmp;} //Attention
int len = LOG[b - a];
if (DEP[A0[a][len]] <= DEP[A0[b - (1 << len) + 1][len]]) return A0[a][len]; else return A0[b - (1 << len) + 1][len];
}
void dm(int No, int lch, int rch)
{
int mr0 = T[No].mr;
if (mr0 != INF) { //Attention
T[No].mr = INF;
T[lch].mr = T[lch].lc = T[lch].rc = mr0; T[lch].seg = 1;
T[rch].mr = T[rch].lc = T[rch].rc = mr0; T[rch].seg = 1;
}
}
void opr0(int l, int r, int No)
{
if (l >= l0 && r <= r0) {T[No].mr = T[No].lc = T[No].rc = x0; T[No].seg = 1;} else {
int mid = l + r >> 1, lch = T[No].lch, rch = T[No].rch; dm(No, lch, rch);
if (mid >= l0) opr0(l, mid, lch);
if (mid < r0) opr0(mid + 1, r, rch);
T[No].lc = T[lch].lc; T[No].rc = T[rch].rc; T[No].seg = T[lch].seg + T[rch].seg; //Attention
if (T[lch].rc == T[rch].lc) T[No].seg--;
}
}
void opr1(int l, int r, int No)
{
if (l >= l0 && r <= r0) {
res += T[No].seg; if (x0 == T[No].lc) res--; x0 = T[No].rc;
if (_x1 == INF) _x1 = T[No].lc;
} else {
int mid = l + r >> 1, lch = T[No].lch, rch = T[No].rch; dm(No, lch, rch);
if (mid >= l0) opr1(l, mid, lch);
if (mid < r0) opr1(mid + 1, r, rch);
}
}
int main()
{
int M, a0, b0, w1, LCA0, U0, x1;
char ch;
scanf("%d%d", &n, &M); init_d();
re(i, n) scanf("%d", &w[i]);
re(i, n-1) {scanf("%d%d", &a0, &b0); add_edge0(--a0, --b0);}
prepare();
re(i, M) {
scanf("\n"); ch = getchar();
if (ch == 'C') {
scanf("%d%d%d", &a0, &b0, &w1); LCA0 = LCA(--a0, --b0);
if (SZ[a0] == 1 && !E[FA[a0]].Z) {w[a0] = w1; a0 = E[FA[a0]].a;} //Attention
while (DEP[a0] >= DEP[LCA0]) { //Attention
U0 = UP[a0]; if (DEP[U0] >= DEP[LCA0]) l0 = 0; else l0 = ord[LCA0]; r0 = ord[a0]; x0 = w1; opr0(0, tot[a0] - 1, root[a0]);
if (DEP[U0] >= DEP[LCA0]) a0 = U0; else a0 = LCA0;
if (FA[a0] != -1) a0 = E[FA[a0]].a; else break; //Attention
}
if (SZ[b0] == 1 && !E[FA[b0]].Z) {w[b0] = w1; b0 = E[FA[b0]].a;} //Attention
while (DEP[b0] >= DEP[LCA0]) { //Attention
U0 = UP[b0]; if (DEP[U0] >= DEP[LCA0]) l0 = 0; else l0 = ord[LCA0]; r0 = ord[b0]; x0 = w1; opr0(0, tot[b0] - 1, root[b0]);
if (DEP[U0] >= DEP[LCA0]) b0 = U0; else b0 = LCA0; //Attention
if (FA[b0] != -1) b0 = E[FA[b0]].a; else break;
}
} else {
scanf("%d%d", &a0, &b0); LCA0 = LCA(--a0, --b0); res = 0; x1 = INF; //Attention
if (SZ[a0] == 1 && !E[FA[a0]].Z) {res++; x1 = w[a0]; a0 = E[FA[a0]].a;}
while (DEP[a0] >= DEP[LCA0]) { //Attention
U0 = UP[a0]; if (DEP[U0] >= DEP[LCA0]) l0 = 0; else l0 = ord[LCA0]; r0 = ord[a0]; x0 = _x1 = INF; opr1(0, tot[a0] - 1, root[a0]);
if (x1 == x0) res--; x1 = _x1;
if (DEP[U0] >= DEP[LCA0]) a0 = U0; else a0 = LCA0;
if (FA[a0] != -1) a0 = E[FA[a0]].a; else break; //Attention
}
x1 = INF;
if (SZ[b0] == 1 && !E[FA[b0]].Z) {res++; x1 = w[b0]; b0 = E[FA[b0]].a;} //Attention
while (DEP[b0] >= DEP[LCA0]) { //Attention
U0 = UP[b0]; if (DEP[U0] >= DEP[LCA0]) l0 = 0; else l0 = ord[LCA0]; r0 = ord[b0]; x0 = _x1 = INF; opr1(0, tot[b0] - 1, root[b0]);
if (x1 == x0) res--; x1 = _x1;
if (DEP[U0] >= DEP[LCA0]) b0 = U0; else b0 = LCA0;
if (FA[b0] != -1) b0 = E[FA[b0]].a; else break; //Attention
}
printf("%d\n", --res);
}
}
return 0;
}