从零开始切颗树：树链剖分原理及实现详解

引言

广义的树链剖分指对树上的一系列节点按照某种规则进行划分，使得对树的操作能够转化成对链的操作，并使用其他高效的数据结构来维护链的状态，从而有效地减少了某些运算或操作的代价。而狭义的树链剖分，即指轻重链剖分（_Heavy-light Decomposition_），又称启发式剖分。本文要讲述的是最简单的一种树链剖分的实现，即使用线段树维护的树链剖分。有兴趣的读者可以试着在理解本文的基础上，尝试使用其他数据结构来代替线段树。

原理

为了便于讲解，笔者将整个算法的实现过程分为以下几个步骤：剖分、映射、维护、查询。接下来让我们依次看看每个过程的实现方式及其原理。

剖分

剖分即将树分解为一条条链。轻重链剖分的核心技巧是构造出了轻重结点的概念。正如树可以递归定义一样，我们也可以递归地定义轻重结点。让我们选取某个结点 u 作为讨论的对象，则有：

重结点：若 v 是 u 的一个子结点，且以 v 为根的结点的个数最多，则称 v 是一个重结点，或称 u 的重子结点是 v （亦称 v 是 u 的重儿子）。

轻结点： u 的其他子结点。

重边： u 与其重子结点所连成的边。

轻边： u 与其轻子结点所连成的边。

重链：重边连接而成的链。

轻链：轻边连接而成的链。

经由上文的定义，我们不难推出以下两个性质：

１. 若 v 是 u 的一个轻子结点，则 v 的子结点数必定小与 u 的子结点数的一半。（提示：反证法。）

２. 从根结点到任意结点的路所经过的轻重链的个数必定都小与 logn。

（笔者的参考资料里有两位作者都提到了这两个性质，其中之一在表述时还出现了笔误。笔者以为第二个性质是保证了整个算法的效率，但对于第一个性质，笔者其实并不明白它有什么卵用。如有了解的读者欢迎发送邮件或在 QQ 上为笔者点明。）

接着我们来考虑剖分的具体实现步骤：

父结点、结点的深度、子结点的数量以及重子结点都可以通过一次深度优先搜索（Depth-First-Search, 或称 DFS）得到。（有文章提到使用 BFS 也可以，笔者并未验证，欢迎读者自行测试。）而通过第二次 DFS，我们可以得到重链以及两个非常重要的序列：每个结点的 DFS 序，以及某个 DFS 序所对应的结点。这两个序列将是后续操作的基石。

映射

映射操作是把剖分得到的链以线段树的形式储存并进行维护。在本文的例题里，数据以点权的形式存储。如数据为边权，则只需将某个结点与其父结点之间的边权记作该结点的权值即可。（感谢 julaoczf 指出）

那么，为什么要用线段树来存储？让我们重新回顾一下上一步的操作。在上一步里，我们通过两次 DFS 得到了每个结点的几乎所有有用的信息，而在其中，我们特地保存了结点于 DFS 序互相之间的映射关系（即指每个结点的 DFS 序与某个 DFS 序所对应的结点）。注意一下这里有个技巧：第二次 DFS 时我们优先选择重子结点作为下一层搜索的开始，那么我们得到的 DFS 序会有以下的特性：任意重链上的边在线段树上的位置必定为一个连续的区间。同时，由于 DFS 序本身的特性，我们还会得到一个附带效果：以某个结点为根节点的所有结点在线段树上的位置必定为一个连续的区间。

这样，我们就可以把所有针对树上的路以及子树的查询与修改操作转化为区间操作，而线段树正是用于高效区间操作的利器！

映射操作的具体实现步骤则相对简单，只需以某个 DFS 序所对应的结点为下标对原数据数组构建线段树即可。

查询

树链剖分主要支持两种类型的查询：任意两结点所连成的路的权值之和或其极值、以及以任意结点为根节点的子树的权值之和或其极值。前一种查询的过程本身和求某两个结点的最近公共祖先（LCA）的过程极为相似，而后者更为简单，所以笔者先从后者开始讲解。

假定 u 和 v 是树上的两个结点，且 u 的深度小于 v ，则我们可以按照以下步骤查询 LCA：

１. 判断 u 和 v 是否在同一条重链上，如果是，则 u 就是 LCA(u, v) 。反之，跳转到２。

２. 使 u , v 分别等于他们所在的重链的顶端结点的父结点。

３. 使 u 的深度小与 v ，然后跳转到 1 。

算法的思路十分直观，即让 u 和 v 不断向上收束，直到 u 和 v 在同一条重链上，然后返回其中深度小的那个。

任意两结点所连成的路的权值之和或其极值的查询步骤与求 LCA 相似，只需要在第二步中加入对重链在线段树上对应的区间进行求和与求极值操作即可。

以任意结点为根节点的子树的权值之和或其极值则更为简单。根据映射时得到的附带效果，该问题可以被直接转化为区间求和以及区间求极值问题。这里有个技巧：我们进行 DFS 时首先记录下每一个结点的以其为根节点的子树的大小，随后查询或修改时只需对 [ 每个结点的 DFS 序 , 每个结点的 DFS 序 + 以其为根节点的子树的大小 ] 这个区间进行操作即可。

维护

维护与查询十分类似，第一种维护的核心思想也是在求 LCA 的过程中逐步对线段树进行区间修改操作，而后一种维护则只要直接对区间进行修改操作。具体原理可参照上文的查询，此处笔者不再加以赘述。

复杂度分析

这里我不会，等以后学好了再来补。（其实是懒）

实现样例

//Solution to https://www.luogu.org/problemnew/show/3384
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long INT64;
const int MAXN = (100000 << 2) + 10;
INT64 tag[MAXN];//Lazy_Tag
int val[MAXN];//Original Data

struct Node {
    int left, right;
    INT64 val;
};

Node tree[MAXN];//Segment Tree

void pushdown(int i) {
    int lc = i << 1;
    int rc = (i << 1) + 1;
    tree[lc].val += (tree[lc].right - tree[lc].left + 1) * tag[i];
    tree[rc].val += (tree[rc].right - tree[rc].left + 1) * tag[i];
    tag[lc] += tag[i];
    tag[rc] += tag[i];
    tag[i] = 0;
}

void update(int i, int x, int y, INT64 k) {
    int lc = i << 1, rc = (i << 1) | 1;
    if (tree[i].left > y || tree[i].right < x) return;
    if (x <= tree[i].left && tree[i].right <= y) {
        tree[i].val += (tree[i].right - tree[i].left + 1) * k;
        tag[i] += k;
    } else {
        if (tag[i]) pushdown(i);
        update(lc, x, y, k);
        update(rc, x, y, k);
        tree[i].val = tree[lc].val + tree[rc].val;
    }
}

INT64 query(int i, int x, int y) {
    int lc = i << 1, rc = (i << 1) + 1;
    if (x <= tree[i].left && tree[i].right <= y)
        return tree[i].val;
    if (tree[i].left > y || tree[i].right < x)
        return 0;
    if (tag[i]) pushdown(i);
    return query(lc, x, y) + query(rc, x, y);
}

//Heavy-light Decomposition STARTS FORM HERE
int siz[MAXN];//number of son
int top[MAXN];//top of the heavy link
int son[MAXN];//heavy son of the node
int dep[MAXN];//depth of the node
int faz[MAXN];//father of the node
int tid[MAXN];//ID -> DFSID
int rnk[MAXN];//DFSID -> ID

struct Edge {
    int next, to;
};

Edge edg[MAXN];
int head[MAXN];
int cnt;
int n, m, r, p;

void dfs1(int u, int father, int depth) {
    dep[u] = depth;
    faz[u] = father;
    siz[u] = 1;
    for (int i = head[u]; i; i = edg[i].next) {
        int v = edg[i].to;
        if (v != faz[u]) {
            dfs1(v, u, depth + 1);
            siz[u] += siz[v];
            if (son[u] == -1 || siz[v] > siz[son[u]]) {
                son[u] = v;
            }
        }
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    tid[u] = cnt;
    rnk[cnt] = u;
    cnt++;
    if (son[u] == -1) {
        return;
    }
    dfs2(son[u], t);
    for (int i = head[u]; i; i = edg[i].next) {
        int v = edg[i].to;
        if (v != son[u] && v != faz[u]){
            dfs2(v, v);
        }
    }
}

void add_edge(int u, int v) {
    edg[cnt].to = v;
    edg[cnt].next = head[u];
    head[u] = cnt;
    cnt++;
}

void build(int i, int l, int r) {
    tree[i].left = l;
    tree[i].right = r;
    if (l == r) {
        tree[i].val = val[rnk[l]];
    } else {
        int mid = (l + r) >> 1;
        build(i << 1, l, mid);
        build((i << 1) | 1, mid + 1, r);
        tree[i].val = tree[i << 1].val + tree[(i << 1) + 1].val;
    }
}

void update_path(int x, int y, int z) {
    int fx = top[x], fy = top[y];
    while(fx != fy) {
        if (dep[fx] > dep[fy]) {
            update(1, tid[fx],tid[x], z);
            x = faz[fx];
        } else {
            update(1, tid[fy], tid[y], z);
            y = faz[fy];
        }
        fx = top[x], fy = top[y];
    }
    if (x != y)
        if (tid[x] < tid[y]) update(1, tid[x], tid[y], z);
            else update(1, tid[y], tid[x], z);
    else update(1, tid[x], tid[y], z);
}

INT64 query_path(int x, int y) {
    INT64 ans = 0;
    int fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] >= dep[fy]) {
            ans += query(1, tid[fx], tid[x]);
            x = faz[fx];
        } else {
            ans += query(1, tid[fy], tid[y]);
            y = faz[fy];
        }
        fx = top[x], fy = top[y];
    }
    if (x != y) {
        if (tid[x] < tid[y]) {
            ans += query(1, tid[x], tid[y]);
        } else {
            ans += query(1, tid[y], tid[x]);
        }
    } else ans += query(1, tid[x], tid[y]);
    return ans;
}

INT64 query_subtree(int x) {
    return query(1, tid[x], tid[x] + siz[x] - 1);
}

void update_subtree(int x,int z) {
    update(1, tid[x], tid[x] + siz[x] - 1, z);
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> r >> p;
    for (int i = 1; i <= n; i++) cin >> val[i];
    int u, v, k, x, y, z; cnt = 1;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    for (int i = 1; i <= n; i++) son[i] = -1;
    cnt = 1;
    dfs1(r, -1, 1);
    cnt = 1;
    dfs2(r, r);
    cnt = 1;
    build(1, 1, n);

    while (m--) {
        cin >> k;
        switch (k) {
            case 1 :
                cin >> x >> y >> z;
                update_path(x, y, z);
                break;
            case 2 :
                cin >> x >> y;
                cout << query_path(x, y) % p << "\n";
                break;
            case 3 :
                cin >> x >> z;
                update_subtree(x, z);
                break;
            case 4 :
                cin >> x;
                cout << query_subtree(x) % p << "\n";
                break;
            default : break;
        }
    }
    return 0;
}

参考资料

剖分操作
、原理与实现、原理与证明、查询与修改