BZOJ 2243 [SDOI2011] 染色：樹鏈剖分 + 線段樹維護顏色段

問題

樹上節點有顏色。操作：1) 路徑染色；2) 查詢路徑顏色段數（連續相同顏色算一段）。n, m ≤ 10⁵。

樹鏈剖分 + 線段樹

• 重鏈剖分將路徑分解為 O(log n) 段連續區間（按 dfs 序）。
• 線段樹節點維護：lc 左端顏色，rc 右端顏色，cnt 區間內顏色段數，lazy 標記（-1 表示無）。
• 合併：cnt = lc.cnt + rc.cnt - (lc.rc == rc.lc)。
• 區間染色打標記，下推時覆蓋子節點顏色與段數（段數=1）。

關鍵代碼片段

struct Node { int lc, rc, cnt, lazy; } t[4*N];

void push_up(int id) {
    t[id].lc = t[id<<1].lc;
    t[id].rc = t[id<<1|1].rc;
    t[id].cnt = t[id<<1].cnt + t[id<<1|1].cnt - (t[id<<1].rc == t[id<<1|1].lc);
}

void apply(int id, int color) {
    t[id].lc = t[id].rc = color;
    t[id].cnt = 1;
    t[id].lazy = color;
}

void push_down(int id) {
    if (t[id].lazy != -1) {
        apply(id<<1, t[id].lazy);
        apply(id<<1|1, t[id].lazy);
        t[id].lazy = -1;
    }
}

路徑操作處理

查詢/修改路徑 (u,v)：while top[u] != top[v]，深度大的鏈頭向上跳，處理對應區間；最後同一鏈上處理剩餘區間。查詢時需注意合併順序：從 u 向上跳的段與從 v 向上跳的段拼接時，中間連接點顏色相同要扣除一段。代碼中用 xx, yy 暫存兩側端點顏色輔助合併。

複雜度

預處理 O(n)，單次操作 O(log² n)，總 O((n+m) log² n)，通過 20s 時限。