給定 n 點樹，m 次操作：
C a b c：將路徑 a→b 上所有點染色 cQ a b：查詢路徑 a→b 上顏色段數（連續同色算一段）注意：顏色值可為 0。
O(log n) 段連續區間每個節點維護：
lc：區間最左顏色rc：區間最右顏色sum：區間內顏色段數lazy：懶標記（-1 表示無，否則為統一染色值）void push_up(int o) {
lc[o] = lc[lson];
rc[o] = rc[rson];
sum[o] = sum[lson] + sum[rson] - (rc[lson] == lc[rson]);
}關鍵：左右子區間邊界顏色相同則段數 -1。
void push_down(int o) {
if (lazy[o] != -1) {
lc[lson] = rc[lson] = lazy[o];
lc[rson] = rc[rson] = lazy[o];
sum[lson] = sum[rson] = 1;
lazy[lson] = lazy[rson] = lazy[o];
lazy[o] = -1;
}
}
void modify_path(int x, int y, int color) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
// top[x] 更深，處理 [in[top[x]], in[x]]
update(1, 1, n, in[top[x]], in[x], color);
x = fa[top[x]];
}
// 同一重鏈
if (dep[x] > dep[y]) swap(x, y);
update(1, 1, n, in[x], in[y], color);
}
難點：分段查詢時，相鄰段邊界顏色可能相同，需扣除重複。
int query_path(int x, int y) {
int res = 0, left_color = -1, right_color = -1;
bool first = true;
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
// x 這側：區間 [in[top[x]], in[x]] 是從下往上
// 查詢時需注意方向，或統一查詢再反轉合併
// 這裡採用：收集段資訊再合併
} else {
// y 這側：區間 [in[top[y]], in[y]] 從上往下
}
}
// 同一重鏈處理
// 最後合併所有段資訊
}
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100005;
#define lson (o<<1)
#define rson (o<<1|1)
int n, m, tot;
int c[maxn], fa[maxn], son[maxn], sz[maxn], dep[maxn];
int top[maxn], in[maxn], rnk[maxn];
int lc[maxn*4], rc[maxn*4], sum[maxn*4], lazy[maxn*4];
vector g[maxn];
void dfs1(int u, int f) {
fa[u] = f; sz[u] = 1; son[u] = -1; dep[u] = dep[f] + 1;
for (int v : g[u]) if (v != f) {
dfs1(v, u);
sz[u] += sz[v];
if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp) {
top[u] = tp; in[u] = ++tot; rnk[tot] = u;
if (son[u] == -1) return;
dfs2(son[u], tp);
for (int v : g[u]) if (v != fa[u] && v != son[u])
dfs2(v, v);
}
void build(int o, int l, int r) {
if (l == r) {
lc[o] = rc[o] = c[rnk[l]];
sum[o] = 1; return;
}
int mid = (l+r)/2;
build(lson, l, mid);
build(rson, mid+1, r);
push_up(o);
}
void push_up(int o) {
lc[o] = lc[lson]; rc[o] = rc[rson];
sum[o] = sum[lson] + sum[rson] - (rc[lson] == lc[rson]);
}
void push_down(int o) {
if (lazy[o] != -1) {
lc[lson] = rc[lson] = lazy[o];
lc[rson] = rc[rson] = lazy[o];
sum[lson] = sum[rson] = 1;
lazy[lson] = lazy[rson] = lazy[o];
lazy[o] = -1;
}
}
void update(int o, int l, int r, int L, int R, int color) {
if (L <= l && r <= R) {
lc[o] = rc[o] = color; sum[o] = 1; lazy[o] = color; return;
}
push_down(o);
int mid = (l+r)/2;
if (L <= mid) update(lson, l, mid, L, R, color);
if (R > mid) update(rson, mid+1, r, L, R, color);
push_up(o);
}
struct SegInfo { int lc, rc, sum; bool empty; };
SegInfo query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R) return {lc[o], rc[o], sum[o], false};
push_down(o);
int mid = (l+r)/2;
if (R <= mid) return query(lson, l, mid, L, R);
if (L > mid) return query(rson, mid+1, r, L, R);
SegInfo left = query(lson, l, mid, L, R);
SegInfo right = query(rson, mid+1, r, L, R);
return {left.lc, right.rc, left.sum + right.sum - (left.rc == right.lc), false};
}
SegInfo merge_info(SegInfo a, SegInfo b) {
if (a.empty) return b;
if (b.empty) return a;
return {a.lc, b.rc, a.sum + b.sum - (a.rc == b.lc), false};
}
int query_path(int x, int y) {
SegInfo left_part = {-1, -1, 0, true}, right_part = {-1, -1, 0, true};
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
SegInfo cur = query(1, 1, n, in[top[x]], in[x]);
// 這段是從 x 往上到 top[x]，順序與查詢結果相反
// 需反轉 lc/rc 再合併到 left_part
swap(cur.lc, cur.rc);
left_part = merge_info(cur, left_part);
x = fa[top[x]];
} else {
SegInfo cur = query(1, 1, n, in[top[y]], in[y]);
// 這段是從 top[y] 往下到 y，順序正確
right_part = merge_info(right_part, cur);
y = fa[top[y]];
}
}
if (dep[x] > dep[y]) swap(x, y);
SegInfo mid = query(1, 1, n, in[x], in[y]);
SegInfo ans = merge_info(merge_info(left_part, mid), right_part);
return ans.sum;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
g[u].push_back(v); g[v].push_back(u);
}
dfs1(1, 0); dfs2(1, 1);
build(1, 1, n);
memset(lazy, -1, sizeof(lazy));
char op[5];
while (m--) {
scanf("%s", op);
if (op[0] == 'C') {
int a, b, col; scanf("%d%d%d", &a, &b, &col);
modify_path(a, b, col);
} else {
int a, b; scanf("%d%d", &a, &b);
printf("%d\n", query_path(a, b));
}
}
return 0;
}
lc/rclazy = -1，不能用 0 判斷無標記sum = sumL + sumR - (rcL == lcR)，核心公式sum=1, lc=rc=colorO(n)O(log² n)（log n 段重鏈 × 線段樹 log n）O(n)本題是「樹上路徑修改/查詢 + 區間合併資訊」的經典模板。關鍵在於：
(lc, rc, sum) 三元組支援區間合併掌握此模式，可解決樹上路徑顏色段、最大子段和、括號匹配等眾多問題。
