您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 2243 染色：樹鏈剖分 + 線段樹維護顏色段數

編輯：關於C++

BZOJ 2243「染色」是樹鏈剖分的經典應用：支持路徑區間染色、查詢路徑上顏色段數。本文詳細解析線段樹節點信息設計、push_up 合併邏輯、鏈上查詢時跨鏈顏色段去重的關鍵技巧。

問題建模

樹上 n 個節點，初始各有顏色。
操作：
C u v c：將 u-v 路徑上所有節點染成顏色 c。
Q u v：查詢 u-v 路徑上顏色段數（連續相同顏色算一段）。

樹鏈剖分回顧

重鏈：每個節點選擇子樹最大的兒子延伸。
輕邊：其餘邊。
性質：任意路徑分解為 O(log n) 條重鏈區間。
DFS 序：pos[u] 為 u 在線段樹中的位置，同一重鏈節點位置連續，且越靠近根 pos 越小。

線段樹節點設計

struct Node {
    int l, r;       // 區間範圍
    int lc, rc;     // 左端點顏色、右端點顏色
    int num;        // 區間內顏色段數
    int tag;        // 懶標記：-1 表示無，≥0 表示整段染為該顏色
} seg[MAXN * 4];

關鍵：push_up 合併邏輯

void push_up(int rt) {
    seg[rt].lc = seg[ls].lc;
    seg[rt].rc = seg[rs].rc;
    seg[rt].num = seg[ls].num + seg[rs].num;
    if (seg[ls].rc == seg[rs].lc) seg[rt].num--; // 跨中點同色，段數-1
}

push_down 懶傳播

void push_down(int rt) {
    if (seg[rt].tag != -1) {
        int c = seg[rt].tag;
        seg[ls].tag = seg[rs].tag = c;
        seg[ls].lc = seg[ls].rc = seg[rs].lc = seg[rs].rc = c;
        seg[ls].num = seg[rs].num = 1;
        seg[rt].tag = -1;
    }
}

路徑查詢去重：核心難點

u-v 路徑分解為若干重鏈區間，從 u、v 向上跳至 LCA。區間查詢返回 num、lc、rc。跨區間合併時需判斷相鄰區間的端點顏色是否相同。

雙向查詢策略

u 向上跳：每次查詢區間 [pos[top[u]], pos[u]]，右端點顏色 rc 與上一條鏈的 左端點顏色 比較。
v 向上跳：同理，記錄其左端點顏色。
最終 u、v 在同一重鏈：查詢 [pos[v], pos[u]]（假設 u 深），兩端分別與 u 方向、v 方向的記錄顏色比較。

查詢函數返回結構

struct QueryResult {
    int num, lc, rc;
};

QueryResult query(int rt, int L, int R, int ql, int qr) {
    if (L == ql && R == qr) return {seg[rt].num, seg[rt].lc, seg[rt].rc};
    push_down(rt);
    int mid = (L + R) >> 1;
    if (qr <= mid) return query(ls, L, mid, ql, qr);
    if (ql > mid) return query(rs, mid+1, R, ql, qr);
    auto left = query(ls, L, mid, ql, mid);
    auto right = query(rs, mid+1, R, mid+1, qr);
    QueryResult res;
    res.num = left.num + right.num - (left.rc == right.lc);
    res.lc = left.lc;
    res.rc = right.rc;
    return res;
}

完整查詢邏輯（偽碼）

int queryPath(int u, int v) {
    int ans = 0;
    int lastColorU = -1, lastColorV = -1; // 記錄上一條鏈的端點顏色
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            swap(u, v);
            swap(lastColorU, lastColorV);
        }
        // u 所在鏈較深
        auto res = query(1, 1, n, pos[top[u]], pos[u]);
        ans += res.num;
        if (res.rc == lastColorU) ans--; // 與上一條鏈左端點同色
        lastColorU = res.lc;
        u = fa[top[u]];
    }
    // 同一重鏈
    if (dep[u] < dep[v]) swap(u, v), swap(lastColorU, lastColorV);
    auto res = query(1, 1, n, pos[v], pos[u]);
    ans += res.num;
    if (res.rc == lastColorU) ans--;
    if (res.lc == lastColorV) ans--;
    return ans;
}