笔记

一、定义

树链剖分是树上的操作，把一棵树分成若干条链，并放在线段树上进行线段树的相关操作。

优先将重儿子（子树大小最大的儿子）连在一起放到线段树上，因此也叫“重链剖分”。

下图就是一种剖分方式：

二、基本操作的实现

1. 处理点深，点的父亲，子树大小，重儿子等

没什么好说的，一个 DFS。

cpp

void dfs1(int u, int father) {
    dep[u] = dep[father] + 1;
    fa[u] = father;
    siz[u] = 1;
    int maxx = -1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == father)
            continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > maxx) {
            son[u] = v;
            maxx = siz[v];
        }
    }
}

2. 给一条链标上连续的序号

结合注释理解。

cpp

void dfs2(int u, int topf) {
    idx[u] = ++cnt; // 标号
    wt[cnt] = w[u]; // 将权值丢到新的序号上
    top[u] = topf; // 记录所在链的链头（这条链序号最小的点）
    if (!son[u]) // 没有儿子，返回
        return;
    dfs2(son[u], topf); // 重儿子都在同一条链上，所以链头不用更改
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa[u] or v == son[u]) // 重儿子遍历过了
            continue;
        dfs2(v, v);
        // 对于轻儿子，它肯定要新开一条链（可参照上图 3 → 4 这条链），新开一条链那轻儿子这个点就是链头
    }
}

3. 对两点间权值进行修改/求和操作

如果要求 $4 \to 8$ 的操作，发现除了 LCA $2$ 所在的链外， $u$ 和 $v$ 上方的链都要跑完。

容易发现 LCA 所在的链的链头绝对比其他链的链头要靠上，所以优先处理链头深度大的链，处理完一条链跳到链头的父亲即可进入下一条链。

由于链内序号连续，所以 $u \to t o p_{u}$ 在线段树对应的点即为 $i d x_{t o p_{u}} \to i d x_{u}$ 。

最后都跳到 LCA 所在的链时，直接操作 $i d x_{u} \to i d x_{v}$ 即可。

如果你不求和，比如求最大，改线段树和 query_range 的 $r e t$ 改成取 $max$ 即可。

cpp

void update_range(int x, int y, int v) {
    while (top[x] != top[y]) { // top[x] == top[y] 说明 x 和 y 都已经跳到了 LCA 所在的链
        if (dep[top[x]] < dep[top[y]])
            swap(x, y); // 处理链头深度大的点
        update(1, 1, n, idx[top[x]], idx[x], v); // 线段树
        x = fa[top[x]]; // 跳到下一条链
    }
    if (dep[x] > dep[y])
        swap(x, y); // 同一条链上深度小的点序号更小
    update(1, 1, n, idx[x], idx[y], v);
}
int query_range(int x, int y) {
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        ret = (ret + query(1, 1, n, idx[top[x]], idx[x])) % mod;
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    ret = (ret + query(1, 1, n, idx[x], idx[y])) % mod;
    return ret;
}

4. 对子树权值进行修改/求和操作

根据深搜的性质，一个子树内的点是连在一起搜的，所以它们的序号也必定是连续的，那对应的序号就是 $i d x_{u} \to i d x_{u} + s i z_{u} - 1$ （ $u$ 是这棵子树的根）。

cpp

void update_son(int u, int v) {
    update(1, 1, n, idx[u], idx[u] + siz[u] - 1, v);
}
int query_son(int u) {
    return query(1, 1, n, idx[u], idx[u] + siz[u] - 1);
}

5. 处理边权

把边权放到那条边深度较大的点当点权即可。

需要注意的是，update_range 和 query_range 执行到最后时（即已经跳到 LCA 所在的链时），如果深度小的点是 $x$ ，那么在线段树上修改 / 查询的区间是 $[i d x_{x} + 1, i d x) y]$ ，因为 x 存的是它上面那条边的信息，不应该算进答案里。

6. LCA

树剖可以求 LCA。

跟处理两点间权值的方法一样，沿着链往上跳，跳到 LCA 所在的链上，深度较小的就是 LCA。

cpp

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

7. 树上移动

树剖还可以模拟在树上移动。

如从 $u$ 点向 $v$ 点方向移动 $t$ 步，步数够用就到 $v$ 点停止，不够就沿最短路径走到哪算哪。

为方便，下文用 $d i s (u, v)$ 表示 $u \to v$ 的距离。

显然树上的距离要求 LCA，表示 $d i s (u, v)$ 就是 $d e p_{u} - d e p_{L C A} + d e p_{v} - d e p_{L C A}$ ，那无非就三种情况：

(1). $d i s (u, v) \leq t$ 。

直接跳到 $v$ 。

(2). $d i s (u, L C A) \geq t$ 。

让 $u$ 往上跳 $t$ 步即可。

定义一个函数 $u p (x, y)$ 表示当前在 $x$ 号点，还需要往上跳 $y$ 步，如果 $t o p_{x}$ 离 $x$ 的距离（深度一减就算出来了）大于 $y$ ，就直接跳到链头，否则说明终点在这条链上，终点的序号是 $i d x_{x} - y$ ，弄个 $r i d x$ 看看序号对应哪个点即可。

(3). $d i s (u, L C A) < t < d i s (u, v)$ 。

让 $v$ 往上跳 $d i s (u, v) - t$ 步即可。

cpp

int up(int x, int y) {
    while (1) {
        if (dep[x] - dep[top[x]] + 1 > y)
            break;
        y -= dep[x] - dep[top[x]] + 1;
        x = fa[top[x]];
    }
    return ridx[idx[x] - y];
}
void run(int u, int v) {
    int LCA = lca(u, v);
    int uLCA = dep[u] - dep[LCA];
    int vLCA = dep[v] - dep[LCA];
    int uv = uLCA + vLCA;
    if (uv <= t)
        u = v;
    else if (uLCA > t)
        m = up(m, t);
    else
        m = up(d, dtmp - (t - mtmp));
}

题集

全是模板，没有思维。

一、关键词库

请自行 Ctrl+F 搜索下列关键词：

1. 权值类

1.1 点权

1.2 边权

2. 线段树

2.1 线段树加减操作

2.2 线段树覆盖操作

2.3 线段树取反操作（相反数）

2.4 线段树求和

2.5 线段树求最大

2.6 线段树求最小

3. 树剖拓展

3.1 路径操作

3.2 子树操作

3.3 树剖 LCA

3.4 树上移动

10/11. P4114 Qtree1 / SP375 QTREE - Query on a tree

边权，线段树覆盖操作，线段树求最大，路径操作。

12. P4116 Qtree3

点权，线段树覆盖操作，线段树求最小，路径操作。

笔记

一、定义

二、基本操作的实现

1. 处理点深，点的父亲，子树大小，重儿子等

2. 给一条链标上连续的序号

3. 对两点间权值进行修改/求和操作

4. 对子树权值进行修改/求和操作

5. 处理边权

6. LCA

7. 树上移动

(1). $d i s (u, v) \leq t$ 。

(2). $d i s (u, L C A) \geq t$ 。

(3). $d i s (u, L C A) < t < d i s (u, v)$ 。

题集

一、关键词库

1. 权值类

2. 线段树

3. 树剖拓展

二、题目

1. P1505 [国家集训队] 旅游

2. P2146 [NOI2015] 软件包管理器

3. P2590 [ZJOI2008] 树的统计

4/5. P3038 [USACO11DEC] Grass Planting G / SP12005 GRASSPLA - Grass Planting

6. P3178 [HAOI2015] 树上操作

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

8. P3833 [SHOI2012] 魔法树

9. P4092 [HEOI2016/TJOI2016] 树

10/11. P4114 Qtree1 / SP375 QTREE - Query on a tree

12. P4116 Qtree3

13. P4315 月下“毛景树”

14. P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego

15. P9432 [NAPC-#1] rStage5 - Hard Conveyors

笔记 ​

一、定义 ​

二、基本操作的实现 ​

1. 处理点深，点的父亲，子树大小，重儿子等 ​

2. 给一条链标上连续的序号 ​

3. 对两点间权值进行修改/求和操作 ​

4. 对子树权值进行修改/求和操作 ​

5. 处理边权 ​

6. LCA ​

7. 树上移动 ​

(1). dis(u,v)≤t。 ​

(2). dis(u,LCA)≥t。 ​

(3). dis(u,LCA)<t<dis(u,v)。 ​

题集 ​

一、关键词库 ​

1. 权值类 ​

2. 线段树 ​

3. 树剖拓展 ​

二、题目 ​

1. P1505 [国家集训队] 旅游 ​

2. P2146 [NOI2015] 软件包管理器 ​

3. P2590 [ZJOI2008] 树的统计 ​

4/5. P3038 [USACO11DEC] Grass Planting G / SP12005 GRASSPLA - Grass Planting ​

6. P3178 [HAOI2015] 树上操作 ​

7. P3384 【模板】重链剖分/树链剖分 ​

8. P3833 [SHOI2012] 魔法树 ​

9. P4092 [HEOI2016/TJOI2016] 树 ​

10/11. P4114 Qtree1 / SP375 QTREE - Query on a tree ​

12. P4116 Qtree3 ​

13. P4315 月下“毛景树” ​

14. P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego ​

15. P9432 [NAPC-#1] rStage5 - Hard Conveyors ​

笔记

一、定义

二、基本操作的实现

1. 处理点深，点的父亲，子树大小，重儿子等

2. 给一条链标上连续的序号

3. 对两点间权值进行修改/求和操作

4. 对子树权值进行修改/求和操作

5. 处理边权

6. LCA

7. 树上移动

(1). $d i s (u, v) \leq t$ 。

(2). $d i s (u, L C A) \geq t$ 。

(3). $d i s (u, L C A) < t < d i s (u, v)$ 。

题集

一、关键词库

1. 权值类

2. 线段树

3. 树剖拓展

二、题目

1. P1505 [国家集训队] 旅游

2. P2146 [NOI2015] 软件包管理器

3. P2590 [ZJOI2008] 树的统计

4/5. P3038 [USACO11DEC] Grass Planting G / SP12005 GRASSPLA - Grass Planting

6. P3178 [HAOI2015] 树上操作

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

8. P3833 [SHOI2012] 魔法树

9. P4092 [HEOI2016/TJOI2016] 树

10/11. P4114 Qtree1 / SP375 QTREE - Query on a tree

12. P4116 Qtree3

13. P4315 月下“毛景树”

14. P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego

15. P9432 [NAPC-#1] rStage5 - Hard Conveyors