简介#

树链剖分是将树分割成若干条链，以维护树上信息的算法。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

树链剖分有多种形式，比如重链剖分、长链剖分和用于 Link-Cut Tree 的实链剖分。大多数情况下，树链剖分都指重链剖分。

树链剖分还能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构来维护树上路径的信息。

重链剖分#

对于每个节点：

定义 重子节点 表示其子节点中子树最大的子节点。如果有多个子树最大的子节点，取其一。如果没有子节点，就无重子节点。
定义 轻子节点 表示剩余的所有子节点。
从这个节点到重子节点的边为重边，到轻子节点的边为轻边。
若干条首尾衔接的重边构成重链。把落单的节点也当作重链，那么整棵树就被剖分成若干条重链。

性质#

树上每个节点都属于且仅属于一条重链，所有的重链将整棵树完全剖分。
重链内的 DFS 序是连续的。
一颗子树内的 DFS 序是连续的。

实现#

fa[x] 表示 $x$ 的父亲。
dep[x] 表示 $x$ 的深度。
siz[x] 表示 $x$ 的子树的节点个数。
son[x] 表示 $x$ 的重儿子。
bel[x] 表示 $x$ 所在重链的顶部节点。
id[x] 表示 $x$ 的 DFS 序，也是其在线段树中的编号。
org[x] 表示 DFS 序为 $x$ 所对应的节点编号。

我们进行两遍 DFS 预处理出这些值。第一次 DFS 求出 fa[x]，dep[x]，siz[x] 和 son[x]。第二次 DFS 求出 bel[x]，id[x] 和 org[x]。

void dfs1(int x,int f) {
    siz[x]=1;
    fa[x]=f;
    dep[x]=dep[f]+1;
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==f) continue;
        dfs1(y,x);
        siz[x]+=siz[y];
        if(siz[y]>siz[son[x]]) son[x]=y;
    }
}
void dfs2(int x,int f) {
    id[x]=++cnt;
    org[cnt]=x;
    bel[x]=f;
    if(!son[x]) return;
    dfs2(son[x],f);
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==son[x]||y==fa[x]) continue;
        dfs2(y,y);
    }
}

常见应用#

可以发现，当我们向下经过一条轻边时，所在子树的大小至少会除以二。

因此，对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 $O(\log n)$ 次，因此，树上的每条路径都可以被拆分成不超过 $O(\log n)$ 条重链。

所以，重链剖分从一个节点到根的路径的轻边切换条数是 $\log{n}$ 级别的。

路径维护#

链上的 DFS 序是连续的，可以使用线段树、树状数组维护。

每次选择深度较大的链往上跳，直到两点在同一条链上。

同样的跳链结构适用于维护、统计路径上的其他信息。

int query_path(int x,int y) {
    int ans=0;
    while(bel[x]!=bel[y]) {
        if(dep[bel[x]]<dep[bel[y]]) swap(x,y);
        ans+=query(1,n,1,id[bel[x]],id[x]);
        x=fa[bel[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    ans+=querysum(1,n,1,id[y],id[x]);
    return ans;
}
void fix_path(int x,int y) {
    while(bel[x]!=bel[y]) {
        if(dep[bel[x]]<dep[bel[y]]) swap(x,y);
        fix(1,n,1,id[bel[x]],id[x]);
        x=fa[bel[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    fix(1,n,1,id[y],id[x]);
}

子树维护#

在 DFS 搜索的时候，子树中的节点的 DFS 序是连续的。

这样就把子树信息转化为连续的一段区间信息，处理 id[x] 到 id[x]+siz[x]-1 的区间即可。

求 LCA#

不断向上跳重链，当跳到同一条重链上时，深度较小的节点即为 LCA。

向上跳重链时需要先跳所在重链顶端深度较大的那个。

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

长链剖分#

对于每个节点：

定义 重子节点 表示其子节点中子树最大的子节点。如果有多个子树最大的子节点，取其一。如果没有子节点，就无重子节点。
定义 轻子节点 表示剩余的所有子节点。
从这个节点到重子节点的边为重边，到轻子节点的边为轻边。
若干条首尾衔接的重边构成长链。把落单的节点也当作长链，那么整棵树就被剖分成若干条长链。

长链剖分性质和实现与重链剖分类似，这里就不再展开。

常见应用#

长链剖分从一个节点到根的路径的轻边切换条数是 $\sqrt{n}$ 级别的。

求 k 级祖先#

考虑对整棵树进行长链剖分，并倍增求出每一个节点的 $2^i$ 级祖先。

对于每条长链的链顶节点，设其所在的长链长度为 $d$ ，记录整条长链并求出这个点向上的 $d$ 级祖先。

假设我们找到了询问节点的 $2^i$ 级祖先满足 $2^i<k<2^{i+1}$ 。我们先跳 $2^i$ 级，还需跳 $k−2^i$ 级。显然 $k−2^i<2^i$ 。

根据长链剖分的性质，任意一个节点 $x$ 的 $k$ 级祖先所在长链的长度一定大于等于 $k$ ，所以 $k−2^i<2^i\leq d$ ，其中 $d$ 为当前的 $x$ 所在长链的长度。

由于 $k−2i<d$ ，所以可以先将 $x$ 跳到 $x$ 所在长链的链顶节点上，然后通过预处理的数组求出答案。

int query(int x,int k){
    if(!k) return x;
    x=fa[x][lg[k]],k-=(1<<lg[k]);
    k-=dep[x]-dep[top[x]],x=top[x];
    if(!k) return x;
    return k>0?up[x][k-1]:down[x][-k-1];
}

优化 DP#

一般情况下可以使用长链剖分来优化的 DP 会有一维状态为深度维。

长链剖分可以把维护子树中只与深度有关的信息优化到线性。

我们可以考虑使用长链剖分优化树上 DP。

具体的，每个节点在维护信息的过程中，先继承重儿子的信息，再暴力合并其余轻儿子的信息。