Dolphin's blog
1287 words
6 minutes
树链剖分
2024-06-23
图论
图论
/
树上问题
/
LCA

简介#

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

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

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

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

重链剖分#

对于每个节点：

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

性质#

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

实现#

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

我们进行两遍 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);
    }
}

常见应用#

重链剖分从一个节点到根的路径的轻边切换条数是 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;
}

长链剖分#

对于每个节点：

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

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

常见应用#

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

求 k 级祖先#

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

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

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

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

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

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。

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

左偏树
Link-Cut Tree