染色

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 4529 字
树上路径染色与查询路径颜色段数，连续相同色算
一本通
练习
正文

/*
原题：T1563 「一本通 4.5 练习 3」染色（SDOI2011）
题意：树上路径染色(C a b c)与查询路径颜色段数(Q a b)，连续相同色算同一段。
思路：HLD 拆路径，线段树每个节点维护区间左色 lc、右色 rc、段数 cnt 与覆盖懒标记 set。
合并：cnt = left.cnt + right.cnt - (left.rc == right.lc)。
路径查询用 Info 累加，并翻转处理两段在 LCA 处的方向，避免重复统计 LCA。
复杂度：时间 O((n+m)log^2 n)，空间 O(n)。
易错点：路径两侧合并方向要一致，LCA 处颜色不能重复计段；
颜色可能含 0，故用 -1 作为“空/无覆盖”的哨兵而非 0。
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m;
vector<int> g[MAXN];
int col[MAXN];
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rk[MAXN], tim;
void dfs1(int u, int p){
    fa[u] = p;
    dep[u] = dep[p] + 1;
    sz[u] = 1;
    son[u] = 0;
    for(int v : g[u]){
        if(v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++tim;
    rk[tim] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int v : g[u]){
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
int lc[4 * MAXN], rc[4 * MAXN], cnt[4 * MAXN], setv[4 * MAXN];
struct Info {
    int l, r, c;
};
Info merge(Info a, Info b){
    if(a.c == 0) return b;
    if(b.c == 0) return a;
    Info x;
    x.l = a.l;
    x.r = b.r;
    x.c = a.c + b.c - (a.r == b.l);
    return x;
}
Info reverse(Info x){
    swap(x.l, x.r);
    return x;
}
void pushup(int o){
    lc[o] = lc[o * 2];
    rc[o] = rc[o * 2 + 1];
    cnt[o] = cnt[o * 2] + cnt[o * 2 + 1] - (rc[o * 2] == lc[o * 2 + 1] && rc[o * 2] != -1);
}
void pushdown(int o, int l, int r){
    if(setv[o] != -1){
        int mid = (l + r) / 2;
        setv[o * 2] = setv[o];
        lc[o * 2] = rc[o * 2] = setv[o];
        cnt[o * 2] = 1;
        setv[o * 2 + 1] = setv[o];
        lc[o * 2 + 1] = rc[o * 2 + 1] = setv[o];
        cnt[o * 2 + 1] = 1;
        setv[o] = -1;
    }
}
void build(int o, int l, int r){
    setv[o] = -1;
    if(l == r){
        lc[o] = rc[o] = col[rk[l]];
        cnt[o] = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}
void update(int o, int l, int r, int ql, int qr, int v){
    if(ql <= l && r <= qr){
        setv[o] = v;
        lc[o] = rc[o] = v;
        cnt[o] = 1;
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    if(ql <= mid) update(o * 2, l, mid, ql, qr, v);
    if(qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, v);
    pushup(o);
}
Info seg_q(int o, int l, int r, int ql, int qr){
    if(ql <= l && r <= qr){
        return {lc[o], rc[o], cnt[o]};
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    if(qr <= mid) return seg_q(o * 2, l, mid, ql, qr);
    if(ql > mid) return seg_q(o * 2 + 1, mid + 1, r, ql, qr);
    return merge(seg_q(o * 2, l, mid, ql, qr), seg_q(o * 2 + 1, mid + 1, r, ql, qr));
}
void path_set(int u, int v, int c){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, 1, n, dfn[top[u]], dfn[u], c);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    update(1, 1, n, dfn[u], dfn[v], c);
}
int query_path(int u, int v){
    Info ans = {0, 0, 0}, rev_ans = {0, 0, 0};
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]){
            Info seg = seg_q(1, 1, n, dfn[top[v]], dfn[v]);
            rev_ans = merge(rev_ans, reverse(seg));
            v = fa[top[v]];
        }else{
            Info seg = seg_q(1, 1, n, dfn[top[u]], dfn[u]);
            ans = merge(ans, reverse(seg));
            u = fa[top[u]];
        }
    }
    if(dep[u] > dep[v]){
        Info seg = seg_q(1, 1, n, dfn[v], dfn[u]);
        ans = merge(ans, reverse(seg));
    } else if(dep[v] > dep[u]){
        Info seg = seg_q(1, 1, n, dfn[u], dfn[v]);
        rev_ans = merge(rev_ans, reverse(seg));
    }else{
        Info seg = seg_q(1, 1, n, dfn[u], dfn[u]);
        ans = merge(ans, reverse(seg));
    }
    return merge(ans, reverse(rev_ans)).c;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> col[i];
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    while(m--){
        char op;
        cin >> op;
        if(op == 'C'){
            int a, b, c;
            cin >> a >> b >> c;
            path_set(a, b, c);
        }else{
            int a, b;
            cin >> a >> b;
            cout << query_path(a, b) << "\n";
        }
    }
    return 0;
}
染色

正文

一本通·提高篇的其它内容
