【例題】
[SDOI2011]染色（注：數(shù)據(jù)范圍木有交代，應(yīng)為：點(diǎn)數(shù)N<=10
5，操作數(shù)M<=10
5，所有的顏色C為整數(shù)且在[0, 10
9]之間。
一、樹的路徑剖分當(dāng)中點(diǎn)權(quán)型（點(diǎn)上有權(quán)值而邊上木有）的處理辦法：
（1）找重鏈建線段樹的時(shí)候，w0中存儲tot+1個(gè)數(shù)，為該重鏈自上而下的各點(diǎn)的權(quán)值（例題中為顏色）；
（2）除了父邊是輕邊的葉結(jié)點(diǎn)之外，樹中的每個(gè)結(jié)點(diǎn)都
屬于且僅屬于一條重鏈（根據(jù)定義得到），所以，設(shè)目前待查路徑的兩個(gè)點(diǎn)（也就是路徑的兩端點(diǎn)）為a0和b0，其LCA設(shè)為LCA0，則a0上溯到LCA0的時(shí)候，先判定a0是不是一個(gè)父邊是輕邊的葉結(jié)點(diǎn)，如果是，就對它單獨(dú)處理，并跳到a0的父結(jié)點(diǎn)處開始循環(huán)上溯，否則從a0開始循環(huán)上溯。上溯時(shí)，若UP[a0]木有超越LCA0則上溯到UP[a0]否則上溯到LCA0，找到a0和上溯到的點(diǎn)的ord，再在線段樹中處理，處理完后，跳到a0的父結(jié)點(diǎn)處（這里一定要判定是不是根結(jié)點(diǎn)），如此循環(huán)，直到
超越（等于都不行）LCA0為止（如果LCA0是根，則上溯到根結(jié)點(diǎn)后直接強(qiáng)退）。對于b0類似處理即可；
（3）改值的時(shí)候，對于父邊是輕邊的葉結(jié)點(diǎn)直接改，對于其它結(jié)點(diǎn)在其所在重鏈對應(yīng)的線段樹中改；
二、路徑的銜接問題的處理辦法：
例題中由于要統(tǒng)計(jì)顏色段數(shù)，涉及到各重鏈之間（包括LCA0附近）的銜接問題，這個(gè)問題在點(diǎn)權(quán)型和邊權(quán)型樹中的處理辦法不同。
下面照樣設(shè)目前待查路徑的兩個(gè)點(diǎn)（也就是路徑的兩端點(diǎn)）為a0和b0，其LCA設(shè)為LCA0。
（1）對于點(diǎn)權(quán)型樹：
先考慮a0上溯到LCA0中的情況。在此過程中需要設(shè)置“最新點(diǎn)”（準(zhǔn)確來說是最新點(diǎn)的權(quán)值，即顏色）x0，一開始給x0賦一個(gè)不可能存在的值（比如-1、INF等）。首先，如果a0是一個(gè)父邊是輕邊的葉結(jié)點(diǎn)，則特判過程中需要先將最新點(diǎn)設(shè)為a0（的權(quán)值），然后在上溯的時(shí)候，不斷將最新點(diǎn)改為UP[a0]，每次跳到父結(jié)點(diǎn)的時(shí)候比較跳到的點(diǎn)與最新點(diǎn)之間的顏色是否相同來進(jìn)行銜接。對于b0上溯到LCA0的情況類似。不過還有一個(gè)地方，就是LCA0附近的銜接，這個(gè)在點(diǎn)權(quán)型樹的處理辦法是：先將“a0->LCA0”與“B0->LCA0"當(dāng)成兩條鏈（顯然都包括LCA0），分別處理后，將這兩條鏈銜接起來，由于它們都包括LCA0，銜接處顏色必定相等，故直接減1即可（注意這只是對于本題而言，對于其它題目還是那句話“具體情況具體分析”）
（2）對于邊權(quán)型樹：
需要設(shè)置的是“最新邊”（一開始最新邊都是不存在的）。上溯過程中存在輕重邊之分，對于輕邊，直接將其與最新邊銜接再將最新邊改為這條邊即可，對于重鏈，將其最后一條邊（注意在線段樹中是最右的，可在過程中記錄）與最新邊銜接，再將最新邊改為這條重鏈的第一條邊（線段樹中最左的，同樣可在過程中記錄）即可。對于“a0->LCA0”與“B0->LCA0"的最右的邊的銜接問題，直接比較即可。
三、一些易疵點(diǎn)和細(xì)節(jié)問題（新發(fā)現(xiàn)的，補(bǔ)充，見代碼中標(biāo)Attention的地方）：
（1）對于prepare的第4步，深搜的時(shí)候，不要把邊的編號（st[i]）與點(diǎn)的編號（i、j）搞混了，回溯的條件應(yīng)是st[i]==i而不是j==i；
（2）求LCA的時(shí)候一定不要忘了“b<a"的情況（要交換），另外LCA可以作為一個(gè)函數(shù)來搞，省得每個(gè)操作都寫；
（3）上溯的時(shí)候，對于點(diǎn)權(quán)型，不要忘了初始的特判、循環(huán)終止條件（超越LCA0）以及跳到父結(jié)點(diǎn)時(shí)對根結(jié)點(diǎn)的處理；
（4）其實(shí)，各個(gè)操作的上溯過程是可以寫成專門的函數(shù)的（當(dāng)然本沙茶在本例題中木有這樣做）；
（5）維護(hù)線段樹中記錄的信息的時(shí)候，別搞疵了（本沙茶一開始在opr0中忘了維護(hù)lc和rc……）；
（6）線段樹下放標(biāo)記的時(shí)候一定要判斷有木有標(biāo)記；
（7）關(guān)于LCA的求法，NZK神犇（Orz！?。。┍硎居胁恍枰柚鶵MQ或者倍增，直接求的，關(guān)鍵是本沙茶還木有搞懂；
（8）調(diào)試技巧是很重要的，可以省去大量的讀程序、對拍的時(shí)間，甚至可能不用對拍（不過本沙茶太若了還不能實(shí)現(xiàn)這一點(diǎn)）；
代碼：
#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;
}