树链剖分不详解

· · 算法·理论

更新记录：

树链剖分の作用：

树链剖分将一个树划分为一个个链，使得更新后的编号能够使用各类数据结构来维护。如线段树。

重链剖分

重链剖分の一些概念：

如图，加粗节点是重儿子，未加粗节点是轻儿子，红圈圈出的链是重链。

重链剖分の主要步骤：

第一步，定义各类变量：

定义如下变量：

还要实现维护所用的数据结构：如线段树。数据结构建议封装或写入一个结构体处理。

其中 e,h,fa,id,son,top,size,d 一般放入结构体中。

code：

struct V{
    vector<int> e;
    int h;
    int fa;
    int id;
    int son;
    int top;
    int size;
    long long d;
} v[N];

int rk[N];

struct msjjg{ // 某数据结构
    // ...
};
// 或
namespace MSJJG{ // 某数据结构
  // ...
}

第二步，跑一遍 dfs

code：

inline void dfs1(int u, int f, int d) {
    v[u].h = d;
    v[u].fa = f;
    v[u].size = 1;

    int cnt = -114514;

    for(auto to: v[u].e) {
        if(to == f) continue;
        dfs1(to, u, d + 1);
        v[u].size += v[to].size;
        if(v[to].size > cnt) cnt = v[to].size, v[u].son = to;
    }
}

主要处理 h,fa,size,son 的信息。

第三步，再跑一遍 dfs

code：

inline void dfs2(int u, int top) {
    v[u].top = top;
    v[u].id = ++_cnt;
    rk[_cnt] = u;
    if(!v[u].son) return;
    dfs2(v[u].son, top);
    for(auto to : v[u].e) {
        if(to == v[u].son) continue;
        if(to == v[u].fa) continue;
        dfs2(to, to);
    }
}

主要处理 top,id,rk 的信息。

第四步，树链剖分相关函数

这里以树链剖分模板题举例。

对于查询/修改子树

这里就不放代码，因为是修改/查询子树，而一个子树内的编号是连续的，所以修改/查询的区间就是 [id_x, id_x + size_x)。

对于修改路径内的节点

code：

inline void add(int x, int y, long long c) {
    while(v[x].top != v[y].top) {
        if(v[v[x].top].h < v[v[y].top].h) x ^= y, y ^= x, x ^= y;
        tree.add(1, v[v[x].top].id, v[x].id, c);
        x = v[v[x].top].fa;
    }
    if(v[x].id > v[y].id) x ^= y, y ^= x, x ^= y;
    tree.add(1, v[x].id, v[y].id, c);
}

就是让深度最低的节点不断向上跳，直到 x 与 y 属于一个重链。而向上跳时，对于重链，编号一定连续，直接线段树修改，后将深度最低的节点跳至其所属重链顶端的父节点，因为其所属重链的顶端已经被修改，所以跳至父节点。如果 x 与 y 属于了一个重链，直接修改 x 到 y。

对于查询路径内的节点

code：

inline long long ask(int x, int y) {
    long long ans = 0, fx = v[x].top, fy = v[y].top;
    while(fx != fy) {
        if(v[fx].h >= v[fy].h)
            ans += tree.ask(1, v[fx].id, v[x].id), x = v[fx].fa, fx = v[x].top;
        else
            ans += tree.ask(1, v[fy].id, v[y].id), y = v[fy].fa, fy = v[y].top;
            ans %= p;
    }
    if(v[x].id <= v[y].id)
        ans += tree.ask(1, v[x].id, v[y].id);
    else 
        ans += tree.ask(1, v[y].id, v[x].id);
        ans %= p;
    return ans;
}

意思与修改差不多，故不做解释。

第五步，实现主函数

没什么要点，不做讲解。

对于时间复杂度の证明

重链剖分的时间复杂度是 O(n\log^2 n)。

怎么证明呢？

重链剖分中每个节点到根的路径最多有 \log n 条轻边。因为如果 fa \to u 的边是一条轻边，那么 fa 的子树大小一定 \ge u 的子树大小，因为重儿子的子树一定 \ge u 的子树大小。而重链剖分中是按重链的 top 来跳的，又因最多 \log n 条轻边，所以最多跳 \log n 次。而每次又会进行数据结构的查询操作，使用数据结构的区间操作单次普遍是 O(\log n) 的，所以重链剖分的时间复杂度是 O(n \log^2 n)。

P3384 【模板】重链剖分/树链剖分

模板题，不做讲解。

code。

SP6779 GSS7 - Can you answer these queries VII

建议做完 P4513 小白逛公园 后，再做此题。

对于每个线段树上节点要额外维护的如下：

对于上传

其余的问题，主要就是查询上的问题。

查询部分的代码：

inline V ask(int x, int y) {
    V l, r;
    long long fx = v[x].top, fy = v[y].top;
    while(fx != fy) {
        if(v[fx].h >= v[fy].h) {
            V _z = l, _y = tree.ask(1, v[fx].id, v[x].id);
            pu(l, _y, _z), x = v[fx].fa, fx = v[x].top;
        }
        else {
            V _z = r, _y = tree.ask(1, v[fy].id, v[y].id);
            pu(r, _y, _z), y = v[fy].fa, fy = v[y].top;
        }
    }
    if(v[x].id <= v[y].id) {
        V _z = r, _y = tree.ask(1, v[x].id, v[y].id);
        pu(r, _y, _z);
    }
    else  {
        V _z = l, _y = tree.ask(1, v[y].id, v[x].id);
        pu(l, _y, _z);
    }
    V yr_ak_ioi;
    swap(l.lans, l.rans);
    return pu(yr_ak_ioi, l, r);
}

基本没什么问题吧，可能有问题的两个地方：

注：举例中相同颜色的一段表示这些点权所在的点在同一个重链。

code。

P4114 Qtree1

这道题与普通的树链剖分的区别：普通是点权，这个是边权。

对于给出的一个树，可能是这样的：

考虑边权下放至深度更低的节点的点权。

如图所示：

那么修改操作就为单点修改。

那对于查询操作呢？

还是上幅图，对于查询 4 到 6 之间的路径。

会发现计算的最大值会考虑多余的最大公共祖先 3 的点权。即计算最大值时，不应该算上最近公共祖先。

那么，两点不在一条重链时，还是按照普通的来跳。

但在一条重链时，只能求最深的节点到最浅的节点的重儿子。即最浅节点的编号 + 1。

code。

P2486 [SDOI2011] 染色

与 SP6779 类似，对于每个线段树上节点只需额外维护以下信息：

对于上传节点：

code。

P4312 [COI 2009] OTOCI

这道题看似需要用 LCT 来做，实际用树链剖分来做也可以。因为题目保证所有的加边操作完成后一定是个森林，而且不强制要求在线，所以可以先用并查集来直接进行加边操作。将最后形成的森林的边确定后，就直接进行树链剖分。然后再用并查集进行所有操作的模拟。

注意：由于形成的可能是森林而不是树，所以要 for(int i = 1; i <= n; i++) if(!v[i].h) dfs1(i, 0, 1), dfs2(i, i); 这么写。

code。

P7735 [NOI2021] 轻重边

这道题是 P2486 [SDOI2011] 染色 的类似题。

对于操作 1. 考虑对点进行染色。

如：

对于样例这颗树：

先对每个点染一个不同的颜色：

那么对于操作一，就是对 a \to b 的路径进行染色。

而对于操作二，就是求 a \to b 求有多少个相邻的同色点。

对于样例的第一个操作，即是 1 \to 7 重新染一个与之前完全不同的颜色：

对于样例的第二个操作，1 \to 4 之中，只有 (1, 3) 这两个相邻的点同色，所以答案是一。

接下来就是普通的树剖（注意查询时合并的顺序）。

code。

P3979 遥远的国度

一道典型的换根树剖。

因为每次换根就重构一次明显会 TLE，所以考虑维护一个假根，再定义一个 rt 记录真的根，最后大力分类讨论即可。

对于操作 1，直接更新 rt 即可。

对于操作 2，直接按照普通的更新就可以了。

对于操作三，大力分讨。为了方便，先假设假根是 1，查询是 x 的子树，绿色节点表示在给出的条件下 rt 能取的节点。

code。

P4211 [LNOI2014] LCA

这是一道区间 LCA 深度和。因为深度是 deep，于是考虑使用 deepseek

求 LCA 的深度，有一种很弱智聪明的做法：假设对点 x 和 y 求 LCA，先让 x 往根跳，对 x 跳时经过的节点打上标记，再让 y 往上跳，y 遇到第一个有标记的节点，假设是 z。那么 z 就是 x 和 y 的 LCA，LCA 的深度就是 z 的深度。这种方法的最劣复杂度是 O(n)。

$O(qn\log^2n)$ 的时间复杂度也是会 TLE。由于问题可以离线，所以采用离线思想。 将 $\sum^{r}_{i = r} dep_{\operatorname{LCA(i,z)}}$，拆为 $\sum^{l - 1}_{i = 1} dep_{\operatorname{LCA(i,z)}}- \sum^{r}_{i = 1} dep_{\operatorname{LCA(i, z)}}$。 对于行如 $\sum^{j}_{i = 1} dep_{\operatorname{LCA(i,z)}}$ 的求和，按照 $j$ 来排序。 然后分别求出前缀和，再求出区间正确的答案。 时间复杂度被优化到了 $O((n + q) \log^2 n)

code。

这里特别鸣谢@yr409892525因为他让我大力压行。

P3401 洛谷树

考虑使用一个位运算相关题目中较为常用的技巧：拆位。

分别统计第 i 位上两点间的异或值为 1 的点对数，再将第每一位上对答案的贡献求和即可。

那么怎么统计第 i 位上点间的异或值为 1 的点对数呢？

由于我太蒟，所以只会一个十分笨拙的写法。

考虑类似区间最大子段和的方法，对于每个线段树节点额外统计以下信息：

那该如何合并呢？

假设要合并的节点是 a,b，要和到节点 c 中。

那么 c 的信息该这样合并：

接下来就是普通的树剖了，还有要注意要按照 SP6779 GSS7 - Can you answer these queries VII 的方法进行区间的查询。

code

P5478 [BJOI2015] 骑士的旅行

这题写了个题解，就去看题解吧：【传送门】。

长链剖分

长链剖分の一些概念：

和重链剖分十分相似，可以参考重链剖分的部分，唯一区别在于是按照子树深度最大来定义重儿子的。

如图，加粗节点是重儿子，未加粗节点是轻儿子，红圈圈出的链是轻链。

长链剖分的用处

很明显，这个东西一定有什么特别的用处，否则发明这个的人一定是吃饱了撑着，所以这个有什么用呢？常见的用处就是解决一些关于深度的一部分问题，以及优化树形DP。

长链剖分的例题

就拿 P5903 【模板】树上 K 级祖先 来作例题。

分析

首先这道题如果直接倍增暴力做 O(n \log n + q \log n) 说是会被卡，但是实际卡没卡也不知道。所以还是要考虑每次询问 O(1) 的解法。

那如何做呢？不难想到，可以利用预处理降低查询的复杂度，所以思路就有了，具体维护就可以维护每条轻链链定分别向上和向下走的数组，每次询问先向上走 2^{t\text{的二进制最高位}}，此时就可以直接查询了。

第一步，定义维护的内容

对于此题，我们总共要维护以下内容：

第二步，处理出重儿子

和重链剖分极其类似，只是判断条件变了。

inline void dfs(LL u, LL fa, LL h) {
    v[u].h = h, f[u][0] = fa, v[u].s = v[u].h;
    for(auto to: v[u].e) {
        if(to == fa) continue;
        dfs(to, u, h + 1);
        if(v[to].s > v[u].s) v[u].s = v[to].s, v[u].son = to;
    }
}

第三步，处理链

也是和重链剖分极为相似。

inline void dfs2(LL u, LL top) {
    v[u].top = top, len[top]++;
    if(v[u].son) dfs2(v[u].son, top);
    for(auto to: v[u].e) {
        if(to == f[u][0]) continue;
        if(to == v[u].son) continue;
        dfs2(to, to);
    }
}

第四步，进行预处理。

这一步主要是预处理 i,a 和 p，也是非常简单，没有技术含量。

for(LL i = 1; i < L; i++) for(LL j = 1; j <= n; j++) f[j][i] = f[f[j][i - 1]][i - 1];
    for(LL i = 1; i <= n; i++) {
        if(v[i].top != i) continue;
        LL x = i;
        for(LL j = 1; j <= len[i]; j++) {
            if(v[x].son == 0) break;
            x = v[x].son;
        }
        for(LL j = 1; j <= len[i] * 2; j++) {
            v[i].a.push_back(x);
            x = f[x][0];
            if(x == 0) break;
        }
    }
    for(LL i = 1; i <= n; i++) {
        for(LL j = L - 1; j >= 0; j--) {
            if((i >> j) > 1) {
                h[i] = j + 1;
                break;
            }
        }
}

第五步，对于答案进行计算。

这里我为了我使用了分讨。

  3. 先往上跳 2^{p_k}，剩下的 k，一定小于原来 k 的二分之一，再直接暴力查表。
for(LL i = 1; i <= q; i++) {
    LL x = (RAND::get(RAND::s) ^ last_ans) % n + 1, k = (RAND::get(RAND::s) ^ last_ans) % v[x].h;
        if(k == 0) {
            cnt ^= i * x;
            last_ans = x;
            continue;
        }
        if(k - (1 << h[k]) == 0) {
            cnt ^= i * f[x][h[k]];
            last_ans = f[x][h[k]];
            continue;
        }
        x = f[x][h[k]];
        k -= (1 << h[k]);
        cnt ^= i * v[v[x].top].a[len[v[x].top] - v[x].h + v[v[x].top].h + k - 1];
        last_ans = v[v[x].top].a[len[v[x].top] - v[x].h + v[v[x].top].h + k - 1];
}

注意：应为我的深度是存在结构体里的，所以讲解中的 p 在代码实现中是全局的 h。

关于正确性的证明

对于这道题，详细有不少人都对于这个处理的正确性感到怀疑（这就是为什么我中间已知没更5个月，因为很懵所以摆了），而且绝大部分题解都没有给出证明。其实这个还是比较容易去想的，可以根据跳的步数一定大于剩余步数，以及自行构造几组数据，然后再根据长剖按深度为重儿子的特点，就可以证明了。

code。

::::info[证明过程]

挖坑待填……

::::

由于我刚学OI，所以没刷几道树链剖分的题。所以只能给出这些了。之后也许还会再加入有些题目。

主要参考资料与题单：

  1. OIwiki。
  2. @Hoks 的 『应用（折磨）篇』重链剖分 和 『应用（折磨）篇』重链剖分 Part 2。
  3. 同样是@Hoks 的 『从入门到入土』树链剖分学习笔记。