树链剖分之从入门到入土 —— ylxmf2005的OI教程

前言

前置芝士:

  1. DFS 序($DFN$)
  2. 线段树(树状数组也行)
  3. 树形动归的基础
  4. 最近公共祖先(不必须,但是推荐)

定义

树链剖分实际上是把一棵树拆成若干个不相交的链,然后用一些数据结构去维护这些链,每条链内点的编号都是连续的。有下面的基础定义:

  1. 一个节点的大小:以该节点为根的子树大小。用 $sz_x$ 来表示。
  2. 重儿子:一个节点的重儿子定义为他所有儿子中最大的那个,如果有多个相同大小的话任取一个。
  3. 重边:链接一个节点与它的重儿子的边。
  4. 轻儿子:一个节点除了重儿子外所有的点。
  5. 轻边:连接一个点与它轻儿子的边。
  6. 重链:首尾相连的重边(没有轻链),把落单的结点也当作重链。

下面是来自网络上的一张图,结合图片食用:

《树链剖分之从入门到入土 —— ylxmf2005的OI教程》

讲解

首先,我们进行第一遍 DFS。

我们指定一个点为根节点,开始 DFS。我们可以在 DFS 的过程中轻松的求出每个子树的大小 $sz_x$,与每个节点的父亲 $fa_x$,每个节点的深度 $dep_x$。我们还可以求出每个节点的重儿子 $son_x$。这就是我们的第一遍 DFS,可以说是预处理。

我们仔细观察一下上图,你会发现什么?最重要的是:我们的每一条重链,它的节点编号都是连续的。

有了第一遍 DFS,肯定有第二遍 DFS 辣。第二遍 DFS 的时候,我们要求出每一条重链是从哪个节点开始的,也就是求出每条重链最顶端的节点,我们称它为 $top$。还要求出每个节点的时间戳 $dfn_x$。相信这对你很容易,要注意的一点是我们要先处理重儿子再处理轻儿子哦,不然的话你不一定能保证重链的时间戳是连续的

那么问题来了:我们如何快速求出一个点到另一个点的最短路径都包含那些节点呢?我举个栗子吧,假设我们要求的是从 $x$ 到 $y$ 的最短路径:

《树链剖分之从入门到入土 —— ylxmf2005的OI教程》

发现 $dep_{top_y} < dep_{top_x}$,所以 $x$ 跳到 $top_x$ 的父亲 $1$,此时发现在一个 $top$ 中了,所以最短路径是 $[6,7], [1,4]$。可以发现,往上跳的次数最多为树高的二倍(实际上是远远不到的),所以复杂度为 $O(n(logn)^2)$。因为几乎达不到,所以可以近似看成常数很大的 $O(nlogn)$。

以上就是最基本的树链剖分了。让我们看一下模板题的代码:

模板

如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:

  1. 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上 $z$

  2. 2 x y 表示求树从x到y结点最短路径上所有节点的值之和

  3. 3 x z 表示将以x为根节点的子树内所有节点值都加上 $z$

  4. 4 x 表示求以x为根节点的子树内所有节点值之和

你可能不知道怎么更新或求子树的所有点值之和,DFS 序下子树点的编号是连续的,所以直接更新或求 $x$ 到 $x + sz_x – 1$ 的权值之和就好了。下面的代码是洛谷的板子(我调了一天,这个树剖总是你怎么看怎么对但他就是 RE 和 WA,希望大家心态不要炸,反正我炸了)。

#include <bits/stdc++.h>
using namespace std; 
#define lson (x << 1)
#define rson (x << 1 | 1)
typedef long long ll;  
const int N = 1e5 + 5; 
inline ll read() {
    ll X = 0, w = 0;  char ch = 0; 
    while(!isdigit(ch)) {w |= ch == '-'; ch = getchar(); }
    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar(); 
    return w ? -X : X; 
}
int n, m, r, p; 
struct edge{
    int to, nxt; 
}e[N << 1]; 
int head[N], tot; 
void addedge(int u, int v){
    e[++tot].to = v; 
    e[tot].nxt = head[u]; 
    head[u] = tot; 
}
int fa[N], sz[N], son[N], dfn[N], b[N], a[N], dep[N], top[N]; 
void dfs1(int u, int f){
    dep[u] = dep[f] + 1; fa[u] = f; sz[u] = 1; 
    for(int i = head[u]; i; i = e[i].nxt){
        if(e[i].to != f){
            dfs1(e[i].to, u); 
            sz[u] += sz[e[i].to]; 
            if(sz[e[i].to] > sz[son[u]]) son[u] = e[i].to; 
        }
    }
}
void dfs2(int u, int topf){
    dfn[u] = ++tot; b[tot] = u; top[u] = topf; 
    if(son[u]) {
        dfs2(son[u], topf); 
        for(int i = head[u]; i; i = e[i].nxt)
            if(!dfn[e[i].to]) dfs2(e[i].to, e[i].to);  
    }
}
struct node{
    int l, r; 
    ll val, add; 
}t[N << 2]; 
void pushdown(int x){
    if(t[x].add){
        t[lson].val += t[x].add * (t[lson].r - t[lson].l + 1); 
        t[rson].val += t[x].add * (t[rson].r - t[rson].l + 1); 
        t[lson].add += t[x].add; 
        t[rson].add += t[x].add; 
        t[x].add = 0; 
    }
}
void pushup(int x){
    t[x].val = (t[lson].val % p + t[rson].val % p) % p; 
}
void build(int x, int l, int r){
    t[x].l = l;  t[x].r = r; 
    if(l == r){
        t[x].val = a[b[l]]; 
        return; 
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);  build(rson, mid + 1, r); 
    pushup(x); 
}
void update(int x, int l, int r, int k){
    if(l <= t[x].l && r >= t[x].r){
        t[x].val += (t[x].r - t[x].l + 1) * k; t[x].add += k; 
        t[x].val %= p; t[x].add %= p; 
        return; 
    }
    pushdown(x); 
    int mid = (t[x].r + t[x].l) >> 1;
    if(l <= mid) update(lson, l, r, k); 
    if(r > mid) update(rson, l, r, k); 
    pushup(x);  
}
ll query(int x, int l, int r){
    ll ans = 0; 
    if(l <= t[x].l && r >= t[x].r) return t[x].val;   
    pushdown(x); 
    int mid = (t[x].r + t[x].l) >> 1;
    if(l <= mid) ans += query(lson, l, r); 
    if(r > mid) ans += query(rson, l, r); 
    return ans % p; 
}
void uptree(int x, int y, int k){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y); 
        update(1, dfn[top[x]], dfn[x], k); 
        x = fa[top[x]]; 
    }
    if(dep[x] > dep[y]) swap(x, y); 
    update(1, dfn[x], dfn[y], k); 
}
ll quetree(int x, int y){
    ll ans = 0; 
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y); 
        ans += query(1, dfn[top[x]], dfn[x]); 
        ans %= p; 
        x = fa[top[x]]; 
    }
    if(dep[x] > dep[y]) swap(x, y); 
    ans += query(1, dfn[x], dfn[y]); 
    return ans % p; 
}
int main(){
    n = read(), m = read(), r = read(), p = read(); 
    for(int i = 1; i <= n; i++) a[i] = read(); 
    for(int i = 1; i < n; i++){
        int u = read(), v = read(); 
        addedge(u, v); 
        addedge(v, u); 
    }
    tot = 0;  
    dfs1(r, 0);  dfs2(r, 0); 
    build(1, 1, n); 
    for(int i = 1; i <= m; i++){
        int opt = read(), x, y, k; 
        if(opt == 1){
            x = read(), y = read(), k = read(); 
            uptree(x, y, k);         
        }
        if(opt == 2){
            x = read(), y = read();  
            printf("%lld\n", quetree(x, y)); 
        }
        if(opt == 3){
            x = read(), k = read(); 
            update(1, dfn[x], dfn[x] + sz[x] - 1, k); 
        }
        if(opt == 4){
            x = read(); 
            printf("%lld\n", query(1, dfn[x], dfn[x] + sz[x] - 1)); 
        }
    }
    return 0; 
}

后记

其实,树链剖分也可以求 LCA,但是你学了基本等于没学。但是我还是贴一下主代码吧:

int lca(int x,int y){
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]]) swap(x,y);
        x = fa[top[x]];    
    }
    if(dep[x]<dep[y]) return x;
    return y;
}

下面给大家推荐几道树链剖分的入门题,前四道题基本上是修改一下模板调一下就可以过(我不会告诉你第一题复制代码就可以过),但是后四道题可能要点智商,实在搞不懂可以学我一样看题解。

  1. 洛谷 P3384 【模板】树链剖分

  2. 洛谷 P3833 [SHOI2012]魔法树(比模板还简单)

  3. 洛谷 P2590 [ZJOI2008]树的统计

  4. 洛谷 P4315 月下“毛景树”

  5. 洛谷 P2486 [SDOI2011]染色

  6. 洛谷 P3925 aaa被续

  7. 洛谷 P3703 [SDOI2017]树点涂色

  8. 洛谷 P3676 小清新数据结构题(zzq AK IOI)

© 2019 ylxmf2005
转载请联系作者

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据