图论——树链剖分

Steadywelkin · 2021-03-30 11:55:06 · 个人记录

树链剖分用于将树分割成若干条链的形式，以维护树上的路径的信息。具体来说就是将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

树链剖分分为以下几种：

• 重链剖分 O(logn)
• 长链剖分 O(\sqrt{n})
• 实链剖分 （用于 Link/cut Tree）

一般在没有特殊说明的情况下，树链剖分默认重链剖分。

重链剖分可以将树上的任意一条路径划分成不超过 O(logn) 条连续的链，每条链上的点深度互不相同，（即是自底而上的一条链，链上所有点的 LCA 为链的一个端点）。

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

例如：

• 修改 树上两点间的路径上 所有点的值
• 查询 树上两点间的路径上 节点权值的 和、极值、其它（在序列上可以用数据结构维护，便于合并的信息）

除了配合数据结构来维护树上的路径信息，树剖还可以用来 O(logn) （且常数小）地求 LCA 。在某些题目中可以利用其性质来灵活地使用树剖。

重链剖分

定义：

• 重子节点：其节点中子树最大的子节点，如果有多个子树最大的子节点，取其一。如果没有子节点就没有重子节点；
• 轻子节点：剩余的所有子节点
• 重边：这个节点到重子节点的边为重边
• 轻边：到其它轻子节点的边为轻边
• 重链：把若干条周围衔接的重边构成重链

把落单的节点也当做重链，那么整棵树就被剖分为若干条重链。

关于实现：

• rnk[x]$ 表示 $DFS$序 中所对应的节点编号，有 $rnk[dfs[x]]=x

分为两次 DFS 操作：

第一次 DFS 是预处理出 fa[x],dep[x],siz[x],son[x]

void prework(int u)
{
    son[u]=-1;
    siz[u]=-1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!dep[v])
        {
            dep[v]=dep[u]+1;
            fa[v]=u;
            prework(v);
            siz[u]+=siz[v];
            if(son[u]==-1 || siz[v]>siz[u])
                son[u]=v;
        }
    }
}

第二次 DFS 求出 top[x],dfn[x],rnk[x]

void dfs(int u,int f)
{
    top[u]=f;
    dfn[u]=++cnt;
    rnk[cnt]=u;
    if(son[u]==-1) return;
    dfs(son[u],f);
    for(int i=head[u];i;i=e[i].next)
        if(e[i].to!=son[u] && e[i].to!=fa[u])
            dfs(e[i].to,e[i].to);
}

树上每一个节点都属于且仅属于一条重链。

重链开头的节点不一定不一定是重子节点（因为重边是对于每一个节点都有定义的）。

所有的重链将整棵树完全剖分。

在剖分时重边优先遍历，最后树的 DFS 序中，重链内的点 dfn 是连续的，按照 dfn 排序后的序列即为剖分后的链。

一棵子树内的 dfn 序是连续的。

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

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

常见应用：

• 求树上两节点之间的路径权值和

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

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

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

• 子树维护

有时会要求，维护子树上的信息，譬如将以 x 为根的子树的所有结点的权值增加 。

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

每一个结点记录 bottom 表示所在子树连续区间末端的结点。

这样就把子树信息转化为连续的一段区间信息。

• 求解最近公共祖先

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

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

关于树链剖分的换根操作

• 换根操作对于两点间的路径修改是没有影响的，因为在一棵树中任意两点之间有且仅有一条路径，所以在换根操作之后，对两点间路径的修改和对两点间路径的查询是可以按照没有换根的情况继续进行的。
• 换根操作对于子树的修改和查询是有影响的，但不能想得过于复杂，其实对于一棵树而言，它本身就是一张图，不过将一个节点上提罢了，所以我们可以研究对于不同的根而言一棵子树的变化规律。

如下图，节点 3 是树中的一棵子树，子树中为 [3,6,7,8]

然后考虑第一种情况：将节点 3 上移至根节点： 发现此时节点 3 以下的子树大小变为了整棵子树的大小。

考虑第二种情况：将不在节点 3 的子树内的一个节点上移作为根节点（图中为节点 2），发现此时的子树大小与原来没有区别，仍然是 [3,6,7,8]

最后考虑第三种情况：将在节点 3 的子树内的一个节点上移作为根节点（图中为节点 8）：发现此时的子树大小就是整棵树的大小减去上提的节点所在的那部分链，这部分链就是在原图中节点 3 到节点 8 的路径上的第一个儿子的整棵子树（注意是子树而不是链）。

综上所述，对于换根操作我们可以这样考虑：

• 将这个节点作为根节点：整棵树
• 将这个节点的子树内的一个节点作为根节点：整棵树 - 在节点内这个节点所在的最大子树
• 以这个节点的子树外的一个节点作为根节点：不变

所以完全不用考虑重新建树，只要对更新与询问操作进行分析就可以实现换根。

长链剖分

长链剖分本质上是另外一种链剖分方式。

定义重子节点表示其子节点中子树深度较大的子节点，如果有多个子树最大的子节点，取其一，如果没有子节点，就无重子节点。

定义轻子节点为剩余的子节点

从这个节点到重子节点的边为重边

到其它轻子节点的边为轻边

若干条首尾相接的重边构成重链

把落单的节点当做重链，那么整棵树就被剖分为若干条重链