树链剖分

2023-02-11 | 阅读：次

===

Index

基础概念
模板
- 使用说明
例题

基础概念

基础概念

重儿子：父节点所有儿子中，子树节点数目最多的节点
重边：父节点和重儿子练成的边
重链：由多条重边连接而成的路径

结论

整棵树会被剖分成若干条重链
轻儿子一定是某条重链的顶点
任意一条路径被切分成不超过log(n)条重链

数组

第一次 dfs 完成下述数组赋值

fa[u]: 存u的父节点
dep[u]: 存u的深度
siz[u]: 存以u为根子树节点数
g[u][0]: 存u的重儿子，dfs过程中会将重儿子交换到g[u][0]位置

第二次 dfs 完成下述数组构建

top[u]: 存u所在重链的顶点
in[u]: 存u剖分后的新编号，即第一次遍历到u时的编号
seq[u]: seq[u] = v, 表示下标为v的节点剖分后的新编号为u, 如果 in[u] = v, 则 seq[v] = u

模板

struct HLD {
    int n, cur = 0;
    vector<int> siz, top, dep, fa, in, out, seq;
    vector<vector<int>> g;
    HLD(int n) : n(n), siz(n), top(n), dep(n), fa(n, -1), in(n), out(n), seq(n), g(n) {}
    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void build(int root = 0) {
        top[root] = root;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (fa[u] != -1)
            g[u].erase(find(g[u].begin(), g[u].end(), fa[u]));

        siz[u] = 1;
        for (auto &v : g[u]) {
            fa[v] = u, dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[g[u][0]]) {
                swap(v, g[u][0]);  // g[u][0] 存储u节点的重儿子
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : g[u]) {
            top[v] = v == g[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) const {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
            else v = fa[top[v]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    int dist(int u, int v) const {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    bool is_anc(int u, int v) const {
        return in[u] <= in[v] && in[v] < out[u];
    }
    int kth_anc(int u, int k) const {
        if (k > dep[u]) return -1;
        int d = dep[u] - k;
        while (dep[top[u]] > d) u = fa[top[u]];
        return seq[in[u] - dep[u] + d];
    }
    bool on_path(int x, int a, int b) const {
        return (is_anc(x, a) || is_anc(x, b)) && is_anc(lca(a, b), x);
    }
    int kth_node_on_path(int a, int b, int k) const {
        int anc = lca(a, b), ls = dep[a] - dep[anc], rs = dep[b] - dep[anc];
        if (k < 0 || k > ls + rs) return -1;
        return k < ls ? kth_anc(a, k) : kth_anc(b, ls + rs - k);
    }
    template<typename F> 
    void path(int u, int v, F &&f) { // 处理从u到v的路径
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            f(in[top[u]], in[u] + 1);
            u = fa[top[u]];
        }
        if (dep[u] < dep[v]) swap(u, v);
        f(in[v], in[u] + 1);
    }
    template<typename F> 
    void tree(int u, F &&f) { // 处理以u为根的子树
        f(in[u], out[u]);
    }
};

使用说明

初始化一个HLD

时间复杂度 O(n), 主要用来初始化各个数组

HLD h(n);

添加边

h.add_edge(u, v); // 0 <= u, v < n

两次dfs构建各种数组

时间复杂度 O(n)

h.build(root);

查询节点u和v的最近公共祖先

int p = h.lca(u, v);

处理树上一条路径的修改与查询问题

根据剖分编号将树上两点间路径转化为不超过log(n)条重链，每条重链的新编号对应一个连续的区间，可以通过线段树维护区间的某些结果。

时间复杂度： O(log(n)*O(T)), O(T) 是一次查询或修改所需要的时间，例如在线段树中为 log(n).

h.path(u, v,[&](int x, int y){
    f(x, y); // seg.apply(x, y, z), seg.get(x, y).sum
});

处理树上一个子树的修改与查询问题

时间复杂度： O(T) 是一次查询或修改所需要的时间，例如在线段树中为 log(n).

h.tree(u, [&](int x, int y){
    f(x, y); // seg.apply(x, y, z);
}); 

例题

树链剖分

洛谷 3384

已知一棵包含 NN 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

x y z，表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。
x y，表示求树从 x 到 y 结点最短路径上所有节点的值之和。
x z，表示将以 x 为根节点的子树内所有节点值都加上 z。
x 表示求以 x 为根节点的子树内所有节点值之和

1 <= n <= 1e5
1 <= m <= 1e5
1 <= r <= n
1 <= p <= 2^31-1

分析

通过树链将路径和子树转化为区间上的查询和修改问题，通过线段树维护。

struct HLD{
// 模板
};
// 懒标记线段树模板

int main() {
    int n, m, r;
    cin >> n >> m >> r >> p;
    r--;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] %= p;
    }

    HLD h(n);

    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        u--, v--;
        h.add_edge(u, v);
    }
    h.build(r);

    LazySegTree<S, op, e, F, tag, merge, id> seg(n);

    for (int i = 0; i < n; ++i) {
        seg.set(h.in[i], {a[i], 1});
    }

    for (int i = 0, op, x, y, z; i < m; ++i) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> z;
            x--, y--;
            z %= p;
            h.path(x, y,[&](int u, int v){
                seg.apply(u, v, z);
            });
        } else if (op == 2) {
            cin >> x >> y;
            x--, y--;
            long long res = 0;
            h.path(x, y,[&](int u, int v){
                res = (res + seg.get(u, v).sum) % p;
            });
            if (res < 0) res += p;
            cout << res << "\n";
        } else if (op == 3) {
            cin >> x >> z;
            x--;
            z %= p;
            h.tree(x,[&](int u, int v){
                seg.apply(u, v, z);
            }); 
        } else {
            cin >> x;
            x--;
            long long res = 0;
            h.tree(x, [&](int u, int v){
                res = (res + seg.get(u, v).sum) % p;
            });
            if (res < 0) res += p;
            cout << res << "\n";
        }
    }
}

路径颜色翻转

hackerearth flip color

一棵n个节点的树，根节点为1，每个节点要么是黑色(用1表示)，要么是白色(用0表示). q次操作，每次给定一个节点编号x，将x及x的所有父节点的颜色翻转。

求q次操作完成后，共有多少个节点是黑色的。

1 <= n, q <= 1e5
1 <= u, v <= n
1 <= x <= n

分析

可以维护每个节点被操作了多少次，使用树链剖分将x 与根节点的路径操作转化为区间操作，通过差分数组维护操作次数，最后统计最终为黑色节点的数目。

struct HLD{
// 模板
};
int main() {
    int n, q;
    cin >> n >> q;
    HLD h(n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];    
    }
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        u--, v--;
        h.add_edge(u,v);
    }
    h.build(0);

    vector<int> d(n + 1);

    for (int i = 0, u; i < q; ++i) {
        cin >> u;
        u--;
        h.path(u, 0, [&](int x, int y){
            d[x]++, d[y]--;
        });
    }
    for (int i = 1;i <= n; ++i) {
        d[i] += d[i - 1];
    }

    int ans = 0;

    for (int i = 0; i < n; ++i) {
        ans += a[h.seq[i]] ^ (d[i] & 1);
    }
    cout << ans << "\n";
}

方法二

可以先预处理每个节点的总共被操作次数，节点u的操作次数等于直接操作u得次数，加所有直接相连的子节点的操作次数。

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];    
    }
    vector<vector<int>> g(n);
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> p(n);
    for (int i = 0, x; i < q; ++i) {
        cin >> x;
        x--;
        p[x]++;
    }

    vector<int> f(n);
    function<void(int, int)> dfs = [&](int u, int fa) {
        f[u] += p[u];
        for (int v : g[u]) if (v != fa) {
            dfs(v, u);
            f[u] += f[v];
        }
    };
    dfs(0, -1);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += a[i] ^ (f[i] % 2);   
    }
    cout << ans << "\n";
}

边权转点权

一棵n个节点的树(编号1-n), 每条边有权重w。q个询问：

1 i w 将第i条边的权重改为w。
2 u v 输出u,v之间的距离
1 <= n, q <= 2e5
1 <= u, v <= n
1 <= w <= 1e9

分析

边权转点权: 对于一条边，将边权赋值给深度更深的节点，处理路径时也需要做一些相应修改。

abc294 G

#include <bits/stdc++.h>
using namespace std;

struct HLD {
    int n, cur = 0;
    vector<int> siz, top, dep, fa, in, out, seq;
    vector<vector<int>> g;
    HLD(){}
    HLD(int n) : n(n), siz(n), top(n), dep(n), fa(n, -1), in(n), out(n), seq(n), g(n) {}
    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void build(int root = 0) {
        top[root] = root;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (fa[u] != -1)
            g[u].erase(find(g[u].begin(), g[u].end(), fa[u]));

        siz[u] = 1;
        for (auto &v : g[u]) {
            fa[v] = u, dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[g[u][0]]) {
                swap(v, g[u][0]);  // g[u][0] 存储u节点的重儿子
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : g[u]) {
            top[v] = v == g[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) const {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
            else v = fa[top[v]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    int dist(int u, int v) const {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    bool is_anc(int u, int v) const {
        return in[u] <= in[v] && in[v] < out[u];
    }
    int kth_anc(int u, int k) const {
        if (k > dep[u]) return -1;
        int d = dep[u] - k;
        while (dep[top[u]] > d) u = fa[top[u]];
        return seq[in[u] - dep[u] + d];
    }
    bool on_path(int x, int a, int b) const {
        return (is_anc(x, a) || is_anc(x, b)) && is_anc(lca(a, b), x);
    }
    int kth_node_on_path(int a, int b, int k) const {
        int anc = lca(a, b), ls = dep[a] - dep[anc], rs = dep[b] - dep[anc];
        if (k < 0 || k > ls + rs) return -1;
        return k < ls ? kth_anc(a, k) : kth_anc(b, ls + rs - k);
    }
    template<typename F> 
    void path(int u, int v, F &&f) { // 处理从u到v的路径
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            f(in[top[u]], in[u] + 1);
            u = fa[top[u]];
        }
        if (dep[u] < dep[v]) swap(u, v);
        if(u != v) f(in[v] + 1, in[u] + 1);
    }
    template<typename F> 
    void tree(int u, F &&f) { // 处理以u为根的子树
        f(in[u], out[u]);
    }
};

struct SegTree {}; 

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n, q;
    cin >> n;
    HLD g(n);
    vector<array<int, 3>> edges;
    for (int i = 0, u, v, w; i < n - 1; ++i) {
        cin >> u >> v >> w;
        u--, v--;
        g.add_edge(u, v);
        edges.push_back({u, v, w});
    }
    g.build();
    SegTree<S, op, e> seg(n);
    for (int i = 0; i < n - 1; ++i) {
        int &u = edges[i][0], &v = edges[i][1], w = edges[i][2];
        if (g.dep[u] > g.dep[v]) swap(u, v);  // 将v交换为节点更深的点
        seg.set(g.in[v], w);  
    }
    cin >> q;
    for (int i = 0, op, x, y; i < q; ++i) {
        cin >> op >> x >> y;
        if (op == 1) {
            x--;
            seg.set(g.in[edges[x][1]], y);     
        } else {
            x--, y--;
            long long ans = 0;
            g.path(x, y, [&](int u, int v){
                ans += seg.get(u, v);
            });
            cout << ans << '\n';
        }
    }
    return 0;
}

边权转点权2

牛客校赛

n个节点的树，每条边有边权，维护以下操作：

1 x y : 查寻节点x到y的路径上边权的平方和模 1e9 + 7
2 x y z : 将节点x到节点y的路径所经过的边的边权增加z
3 x y z : 将节点x到节点y的路径所经过的边的边权修改为z
1 <= n, m <= 1e5
1 <= z <= 5000

struct S {
    mint sum, s2;
    int size;
    S():sum(0),s2(0),size(0){} 
    S(mint s, mint s1, int siz):sum(s),s2(s1),size(siz){}
};

struct F{
    int t;   // t = 0: 赋值， t=1 加和
    mint v;
};

S op(S x, S y) {
    if(x.size==0)return y;
    if(y.size==0)return x;
    return S{x.sum + y.sum, x.s2+y.s2, x.size + y.size};
}
S e() {
    return S{};
};
S tag(F f, S s) { 
    if(f.t == 1 && f.v == 0)return s;
    S res;
    res.size = s.size;
    if (f.t == 0){
        res.sum = s.size * f.v; res.s2 =  (f.v * f.v) * s.size;
    }else{
        res.sum = s.size * f.v + s.sum;
        res.s2 = s.s2 + s.size * (f.v * f.v)+ 2 * s.sum * f.v;
    }
    return res;
}
F merge(F x, F y) { 
    return x.t == 0 ? x : F{y.t, y.v + x.v};
}
F id() { return F{1, 0}; }  //

void ac_yyf(int tt) {
    rd(n,m);
    HLD g(n);
    vector<array<int, 3>> edges;
    for (int i = 0, u, v, w; i < n - 1; ++i) {
        cin >> u >> v >> w;
        u--, v--;
        g.add_edge(u, v);
        edges.push_back({u, v, w});
    }
    g.build();
    LazySegTree<S, op, e, F, tag, merge, id> seg(n);
    for (int i = 0; i < n - 1; ++i) {
        int &u = edges[i][0], &v = edges[i][1], w = edges[i][2];
        if (g.dep[u] > g.dep[v]) swap(u, v);  // 将v交换为节点更深的点
        seg.set(g.in[v], S{w,w*w,1});  
    }
 
    for (int i = 0, op, x, y,w; i < m; ++i) {
        cin >> op;
        if (op==1){
            cin>>x>>y;
            x--,y--;
            if(g.dep[x] > g.dep[y]) swap(x,y);
            mint ans = 0;
            g.path(x, y, [&](int u, int v){
                ans += seg.get(u, v).s2;
            });
            cout << ans << '\n';
        }else if(op==2){
            cin>>x>>y>>w;
            x--,y--;
            if(g.dep[x] > g.dep[y]) swap(x,y);
            g.path(x, y, [&](int u, int v){
                seg.apply(u,v,F{1,w});
            });
        }else{
            cin>>x>>y>>w;
            x--,y--;
            if(g.dep[x] > g.dep[y]) swap(x,y);
            g.path(x, y, [&](int u, int v){
                seg.apply(u,v,F{0,w});
            });
        }
    }
}

加点删点求深度

牛客校赛

n个节点的树，1是根，根的深度为1，q次操作

1 x (2 <= x < n + i) 新增一个编号为 n+i的点，父节点为x。
2 x (2 <= x < n + i) 删除顶点x，将x的所有子节点挂到x的父节点上。
3 x (1 <= x < n + i) 查询节点x的深度
2 <= n, q <= 2e5

void ac_yyf(int tt) {
    int n,q;
    cin>>n>>q;
    vector<int> p(n+q,-1);
    HLD g(n+q);
    f1(n-1){
        int x;
        cin>>x;
        x--;
        p[i]=x;
    }
    vector<vector<int>> qs(q);
    f0(q){
        int op,x;
        cin>>op>>x;
        x--;
        if(op==1){
            p[n+i]=p[x];
            p[x]=n+i;
            qs[i]={op,n+i};
        }else{
            qs[i]={op,x};
        }
    }
    for(int i=0;i<n+q;++i){
        if(p[i]!=-1){
            g.add_edge(p[i],i);
        }
    }
    g.build();

    SegTree<S, op, e> seg(n+q);
    f0(n){
        seg.set(g.in[i],1);
    }
    for(auto&v:qs){
        int op=v[0],x=v[1];
        if(op==1){
            seg.set(g.in[x],1);
        }else if(op==2){
            seg.set(g.in[x],0);
        }else{
            int ans=0;
            while(x>=0){
                int t=g.top[x];
                ans+=seg.get(g.in[t],g.in[x]+1);
                x=g.fa[t];
            }
            cout<<ans<<'\n';
        }
    }
}

路径上最大最小子数组和

cf1843 F2

给定一颗树，每个节点有个权值，q次询问，每次询问给定[x,y]，求x到y的路径上点的权值形成的序列的最大最小子数组和。

分析

最大子数组合并时不满足交换律，因此要注意路径的合并顺序，将路径拆分为x到lca，以及lca到y。

// HLD, segtree
struct S {
    int sum;
    int mxp, mxs, mxans;
    int mnp, mns, mnans;

    S(int x = 0) : sum(x), mxp(std::max(0, x)), mxs(std::max(0, x)), mxans(max(0, x)), mnp(std::min(0, x)), mns(std::min(0, x)), mnans(min(0, x)) {}
    void rev() { swap(mxp, mxs), swap(mnp, mns); }
};

S op(S a,  S b) {
    S res;
    res.sum = a.sum + b.sum;
    res.mxp = std::max(a.mxp, a.sum + b.mxp);
    res.mxs = std::max(b.mxs, b.sum + a.mxs);
    res.mnp = std::min(a.mnp, a.sum + b.mnp);
    res.mns = std::min(b.mns, b.sum + a.mns);
    res.mxans = max({a.mxans, b.mxans, a.mxs + b.mxp});
    res.mnans = min({a.mnans, b.mnans, a.mns + b.mnp});
    return res;
}
S e() {
    return S();
}

void solve() {
    // 省略读数据，建图等。
    vector<array<int, 3>> queries, edges;
    for (auto &[u, v, k] : queries) {
        int c = t.lca(u, v); // 从u到v的路径，t为HLD
        S l, r;
        t.path(u, c, [&](int x, int y){
            l = op(st.get(x, y), l);
        });
        if (v != c) {
            l.rev();
            t.path(v, c, [&](int x, int y){
                if (x == t.in[c]) x++;
                r = op(st.get(x, y), r);
            });
            l = op(l, r);
        }
        if (l.mnans <= k && l.mxans >= k) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

树上倍增

luogu p1967

n个点，m条无向边，每条边有边权。q次询问，每次询问给定两个点(x,y),求x到y的所有路径中经过边权最小值的最大值。如果x,y不连通，输出-1.

1 <= n <= 1e4
1 <= m <= 5e4
1 <= q <= 3e4
1 <= z <= 1e5

分析

如果x,y连通，则x到y的路径的最小值的最大值一定只会走x，y所在连通图的最大生成树之间的边，所以可以对每个联通图先求最大生成树，然后就是求树上两点边权的最小值问题。

树剖

边权转点权，使用st表维护路径最小值即可。

// ST, HLD, DSU, KruscalMST
void ac_yyf(int tt) {
    rd(n,m);

    vector<vector<int>> adj(n);
    vector<array<int, 3>> es(m); 

    for (int i = 0, u, v, w; i < m; ++i) {
        cin >> u >> v >> w;
        u--, v--;
        es[i] = {u, v, w};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> vis(n), id(n), p(n), siz(n);
    int cnt = 0, idx = 0;

    auto bfs = [&](int x){
        vis[x] = 1;
        id[x] = cnt;
        p[x] = idx++;
        queue<int> q;
        q.push(x);
        while(q.size()) {
            auto u = q.front();
            q.pop();
            for (int v : adj[u]) if (!vis[v]) {
                vis[v] = 1;
                id[v] = cnt;
                p[v] = idx++;
                q.push(v);
            }
        }
    };
 
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            idx = 0;
            bfs(i);
            siz[cnt] = idx;
            cnt++;
        }
    }

    vector<maxMst<int>> t(cnt);
    vector<HLD> g(cnt);

    for (int i = 0; i < cnt; ++i) {
        t[i] = maxMst<int>(siz[i]);
        g[i] = HLD(siz[i]);
    }

    for (auto e: es) {
        int u = e[0], v = e[1], w = e[2];
        int k = id[u];
        t[k].add_edge(p[u], p[v], w);
    }

    for (int i = 0; i < cnt; ++i) {
        t[i].build();
        for (auto &[u, v, w] : t[i].es) {
            g[i].add_edge(u, v);
        }
        g[i].build();
    }

    vector<ST<int, op>> s(cnt);

    for (int i = 0; i < cnt; ++i) {
        vector<int> a(siz[i]);
        for (auto &[u, v, w] : t[i].es) {
            if (g[i].dep[u] > g[i].dep[v]) {
                swap(u, v);
            }
            a[g[i].in[v]] = w;
        }
        s[i].build(a);
    } 

    cin >> q;
    for (int i = 0, u, v; i < q; ++i) {
        cin >> u >> v;
        u--, v--;
        int k1 = id[u], k2 = id[v]; 
        if (k1 != k2) {
            cout << "-1\n";
            continue;
        }
        u = p[u], v = p[v];
        int ans = 1e9;
        g[k1].path(u, v, [&](int x, int y){
            ans = min(ans, s[k1].get(x, y - 1));
        });
        cout << ans << '\n';
    }
}

king-yyf

king-yyf

树链剖分

Index

基础概念

模板

使用说明

例题

树链剖分

路径颜色翻转

边权转点权

边权转点权2

加点删点求深度

路径上最大最小子数组和

树上倍增