树剖/dsu on tree/线段树合并【雨天的尾巴】

[Vani有约会]雨天的尾巴

题目链接

一道好板子 甚至能当三个板子（

树链剖分

vector<int> add[maxn], del[maxn];
vector<int> vp[maxn];
int dep[maxn], siz[maxn], son[maxn];
int fat[maxn], top[maxn];

void dfs1(int p, int fa, int dp){
    fat[p] = fa;
    dep[p] = dp;
    son[p] = 0;
    siz[p] = 1;
    for(int v: vp[p]){
        if(v == fa) continue;
        dfs1(v, p, dp+1);
        siz[p] += siz[v];
        if(siz[v] > siz[son[p]]) son[p] = v;
    }
}

void dfs2(int p, int fa, int _top){
    top[p] = _top;
    if(son[p]) dfs2(son[p], p, _top);
    for(int v: vp[p]){
        if(v != fa && v != son[p]){
            dfs2(v, p, v);
        }
    }
}

struct segTree{
    int mx[maxn << 2];
    void pushUp(int p){
        mx[p] = max(mx[p*2], mx[p*2+1]);
    }
    void modify(int p, int l, int r, int pos, int d){
        if(l == r){
            mx[p] += d;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid) modify(p*2, l, mid, pos, d);
        else modify(p*2+1, mid+1, r, pos, d);
        pushUp(p);
    }
    int query(int p, int l, int r){
        if(mx[p] <= 0) return 0;
        if(l == r) return l;
        int mid = (l + r) / 2;
        if(mx[p*2] >= mx[p*2+1]) return query(p*2, l, mid);
        else return query(p*2+1, mid+1, r);
    }
}st;

int n, q;
int ans[maxn];
void calcu(int p, int fa){
    for(int w: add[p]) st.modify(1, 1, 100000, w, 1);
    ans[p] = st.query(1, 1, 100000);
    for(int w: del[p]) st.modify(1, 1, 100000, w, -1);

    if(son[p]) calcu(son[p], p);
    for(int v: vp[p]){
        if(v != fa && v != son[p]) calcu(v, p);
    }
}

void solve(){
    cin >> n >> q;
    for(int i=1;i<n;i++){
        int x, y;
        cin >> x >> y;
        vp[x].emplace_back(y);
        vp[y].emplace_back(x);
    }
    dfs1(1, 0, 1);
    dfs2(1, 0, 1);

    for(int i=1;i<=q;i++){
        int x, y, w;
        cin >> x >> y >> w;
        while(top[x] != top[y]){
            if(dep[top[x]] > dep[top[y]]){
                add[top[x]].emplace_back(w);
                del[x].emplace_back(w);
                x = fat[top[x]];
            }else{
                add[top[y]].emplace_back(w);
                del[y].emplace_back(w);
                y = fat[top[y]];
            }
        }
        if(dep[x] > dep[y]) swap(x, y);
        add[x].emplace_back(w);
        del[y].emplace_back(w);
    }

    calcu(1, 0);
    for(int i=1;i<=n;i++) cout << ans[i] << '\n';
}

dsu on tree

vector<pair<int, int>> tag[maxn];
vector<int> vp[maxn];
int f[maxn][23], dep[maxn], siz[maxn], mxson[maxn];

void dfs(int p, int fa){
    f[p][0] = fa;
    dep[p] = dep[fa] + 1;
    mxson[p] = 0;
    siz[p] = 1;
    for(int v: vp[p]){
        if(v == fa) continue;
        dfs(v, p);
        siz[p] += siz[v];
        if(siz[v] > siz[mxson[p]]) mxson[p] = v;
    }
}

struct segTree{
    int mx[maxn << 2];
    void pushUp(int p){
        mx[p] = max(mx[p*2], mx[p*2+1]);
    }
    void modify(int p, int l, int r, int pos, int d){
        if(l == r){
            mx[p] += d;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid) modify(p*2, l, mid, pos, d);
        else modify(p*2+1, mid+1, r, pos, d);
        pushUp(p);
    }
    int query(int p, int l, int r){
        if(mx[p] <= 0) return 0;
        if(l == r) return l;
        int mid = (l + r) / 2;
        if(mx[p*2] >= mx[p*2+1]) return query(p*2, l, mid);
        else return query(p*2+1, mid+1, r);
    }
}st;

int n, q;
void calcu(int p, int fa, int d){
    for(auto pi: tag[p]){
        st.modify(1, 1, 100000, pi.first, pi.second * d);
    }
    for(int v: vp[p]){
        if(v != fa){
            calcu(v, p, d);
        }
    }
}

int ans[maxn];
void work(int p, int fa, int save){
    for(int v: vp[p]){
        if(v != fa && v != mxson[p]){
            work(v, p, 0);
        }
    }
    if(mxson[p]) work(mxson[p], p, 1);
    for(int v: vp[p]){
        if(v != fa && v != mxson[p]){
            calcu(v, p, 1);
        }
    }
    for(auto pi: tag[p]){
        st.modify(1, 1, 100000, pi.first, pi.second);
    }
    ans[p] = st.query(1, 1, 100000);
    if(!save) calcu(p, fa, -1);
}

void solve(){
    cin >> n >> q;
    for(int i=1;i<n;i++){
        int x, y;
        cin >> x >> y;
        vp[x].emplace_back(y);
        vp[y].emplace_back(x);
    }
    dep[1] = 1;
    dfs(1, 0);
    for(int k=1;k<=20;k++){
        for(int i=1;i<=n;i++){
            f[i][k] = f[f[i][k-1]][k-1];
        }
    }

    auto lca = [](int x, int y){
        if(dep[x] < dep[y]) swap(x, y);
        for(int k=20;k>=0;k--){
            if(dep[f[x][k]] >= dep[y]) x = f[x][k];
        }
        if(x == y) return x;
        for(int k=20;k>=0;k--){
            if(f[x][k] != f[y][k]){
                x = f[x][k], y = f[y][k];
            }
        }
        return f[x][0];
    };

    for(int i=1;i<=q;i++){
        int x, y, w;
        cin >> x >> y >> w;
        int l = lca(x, y);
        tag[x].emplace_back(w, 1);
        tag[y].emplace_back(w, 1);
        tag[l].emplace_back(w, -1);
        tag[f[l][0]].emplace_back(w, -1);
    }
    work(1, -1, 1);
    for(int i=1;i<=n;i++) cout << ans[i] << "\n";
}

线段树合并

struct SegTree{
    int tot = 0;
    int mx[maxn << 5], ls[maxn << 5], rs[maxn << 5], mxp[maxn << 5];
    void push_up(int p){
        mx[0] = -1e9;//注意可能pushup不存在的节点
        if(mx[ls[p]] >= mx[rs[p]]){
            mx[p] = mx[ls[p]];
            mxp[p] = mxp[ls[p]];
        }else{
            mx[p] = mx[rs[p]];
            mxp[p] = mxp[rs[p]];
        }
    }
    int modify(int p, int l, int r, int pos, int d){
        if(!p) p = ++tot;
        if(l == r){
            mx[p] += d;
            mxp[p] = l;
            return p;
        }
        int mid = (l + r) / 2;
        if(pos <= mid) ls[p] = modify(ls[p], l, mid, pos, d);
        else rs[p] = modify(rs[p], mid+1, r, pos, d);
        push_up(p);
        return p;
    }
    int merge(int x, int y, int l, int r){//返回合并后的节点，替代式合并，合并后a这棵线段树就没用了
        if(!x) return y;
        if(!y) return x;//都没有同样return 0
        if(l == r){
            mx[x] += mx[y];
            mxp[x] = l;
            return x;
        }
        int mid = (l + r) / 2;
        ls[x] = merge(ls[x], ls[y], l, mid);
        rs[x] = merge(rs[x], rs[y], mid+1, r);
        push_up(x);
        return x;
    }
}st;

vector<pair<int, int>> tag[maxn];
vector<int> vp[maxn];
int f[maxn][23], dep[maxn];

void dfs(int p, int fa){
    f[p][0] = fa;
    dep[p] = dep[fa] + 1;
    for(int v: vp[p]){
        if(v == fa) continue;
        dfs(v, p);
    }
}

int ans[maxn];
int dfs2(int p, int fa){
    int rt = ++st.tot;
    for(auto pi: tag[p]) st.modify(rt, 1, 100000, pi.first, pi.second);
    for(int v: vp[p]){
        if(v == fa) continue;
        rt = st.merge(rt, dfs2(v, p), 1, 100000);
    }
    if(st.mx[rt] == 0) ans[p] = 0;
    else ans[p] = st.mxp[rt];
    return rt;
}

void solve(){
    int n, q;
    cin >> n >> q;
    for(int i=1;i<n;i++){
        int x, y;
        cin >> x >> y;
        vp[x].emplace_back(y);
        vp[y].emplace_back(x);
    }
    dep[1] = 1;
    dfs(1, 0);
    for(int k=1;k<=20;k++){
        for(int i=1;i<=n;i++){
            f[i][k] = f[f[i][k-1]][k-1];
        }
    }

    auto lca = [](int x, int y){
        if(dep[x] < dep[y]) swap(x, y);
        for(int k=20;k>=0;k--){
            if(dep[f[x][k]] >= dep[y]) x = f[x][k];
        }
        if(x == y) return x;
        for(int k=20;k>=0;k--){
            if(f[x][k] != f[y][k]){
                x = f[x][k], y = f[y][k];
            }
        }
        return f[x][0];
    };

    for(int i=1;i<=q;i++){
        int x, y, w;
        cin >> x >> y >> w;
        int l = lca(x, y);
        tag[x].emplace_back(w, 1);
        tag[y].emplace_back(w, 1);
        tag[l].emplace_back(w, -1);
        tag[f[l][0]].emplace_back(w, -1);
    }
    dfs2(1, -1);
    for(int i=1;i<=n;i++) cout << ans[i] << '\n';
}