链剖分总结

upd on 2024.1.5（浙江首考前一天上日报哩）

由于作者已经 AFO，忙着高考，可能无法及时（也没有能力）对大家的提问做出解答，在此深表遗憾

upd on 2024.6.29

作者回来辣！THUSC 2021 的题目已经可以在洛谷上提交了，更新了题目链接。

这篇文章是我复习链剖分时所写笔记的一部分，希望可以从具体的实践和处理技巧上体现出对一些链剖分算法与问题的理解与感悟。文章中如有错误或表述不清之处，还请各位评论中指出，我一定认真改正（求轻喷qwq）。

这篇文章包含的内容有：

• 重链剖分

• • 性质
• • 全局平衡二叉树
• • 应用，包含动态 dp，dsu on tree，静态（动态）链分治

• 长链剖分

• • 性质
• • 快速求 k 级祖先
• • dsu on tree，优化 dp，节点深度的统计问题，与节点距离有关的统计问题

文章中的例题不会直接贴上代码（那样会看起来比较水），而是会挂在一个云剪切板里

树上 ds 问题的困境

对于树上的数据结构问题，还没有有效的 ds 能够维护，我们目前能做的只有链这种特殊的树（因为它相当于序列）。

于是我们希望可以用一种方式，把一棵树切成若干条链来进行维护。（并不只是 ds 问题，它可以把一些其他的树上问题转换成序列问题，见后）我们把这种切分的方式称为“剖分”。

但剖分也不能随便乱剖，我们做出以下规定：

• 假设树是一个有根树。
• 每个点恰好包含在一条剖出的链中（原因是如果一个点在好几条链中，那么修改这个点的信息时就需要对好几条链进行修改）。
• 每条剖出的链都必须是直链，即链上节点的深度是有序的（这条是为了使描述剖分结构更方便一些）。
• 每条链的下端点为一个叶子（一条长的链从中间断开成几条小的链没有意义）。

有了这些规定，我们就可以描述一个剖分方式了：

对于一个非叶节点 u，恰好存在一个 u 的儿子 v 满足 u,v 在同一条剖出的链之内，称这个儿子为 u 的重儿子（preferred-son），其他儿子称为轻儿子，称 (u,v) 的树边为重边，其他树边为轻边。

记录重儿子信息 son_u=v，定义叶节点的 son 值为 0，很明显一个 son 序列与一种剖分方式一一对应。

在所有这样合法的 son 中，挑出了两种特殊的：

先来看第一个，它也被称为重链剖分。

重链剖分

每条由 u\sim son_u 剖出的链称为重链。

这种剖分方式有一些非常好的性质：

1. 若 v 是 u 的轻儿子，那么有 siz_u>2siz_v。

2. 任意节点到根路径上轻边数量为 O(\log n)。

3. 任意两点间的链上轻边数量为 O(\log n)。

4. 所有重链链顶节点的子树大小之和为 O(n\log n)。

由第三条性质，我们可以把任意点对间的链拆成 O(\log n) 个重链上的区间，并且我们可以快速地找出这些区间：

Decompose(x,y){
    while (top[x]!=top[y]){
        若 dep[top[x]]<dep[top[y]] swap(x,y)
        分解出 [top[x],x] 这一段重链上的区间
        x=fa[top[x]]
    }
    若 dep[x]>dep[y] swap(x,y)
    分解出 [x,y] 这一段重链上的区间
}

这些区间全部都是形态确定的线性结构，在我们眼中，它们与序列无异，因此，可以使用合适的数据结构以区间的方式维护这些重链，从而快速地实现链修改。

存在两种合适的组织数据结构的方式：

1. 使用 dfn 序列，每个点优先向它的重儿子遍历，这样做的好处是同时保证了一个子树在 dfn 序列上是一段区间，而且一条重链在 dfn 序列上也是一段区间，且保留了重链上节点的相对顺序。这样使用一个数据结构维护所有的信息，就能同时支持链操作与子树操作。

2. 每条重链单独使用一个数据结构进行维护，其缺点是不方便子树修改（硬要改也是可以的，把所有开出的数据结构按 dfn 排好，写成树套树的形式），优点是每个重链的结构独立，有更大的调整空间（见后，全局平衡二叉树），同时链修改的常数更小。我们需要额外算出每个节点在重链中的位置。

数据具体的维护方式并不在关于链剖分的讨论之中，接下来默认为使用线段树作为维护信息的数据结构，也就是 单点/区间 半群 修改/查询 的所需时间均为 O(\log n)（当然，半群信息合并的时间不计，这里当作 O(1) 处理）。

这里额外需要补充的一点是在一些情况下查询与修改的互化，比如：

• 到根路径加，单点查，可以转化为单点加，子树查。

• 子树加，单点查，可以转化为单点加，到根路径查。

• 到根路径加，子树查，可以通过深度的分析转化为单点加，子树查。

• 子树加，到根路径查，与上面是类似的。

本质是考虑修改对询问的贡献，在一些情况下可以起到转化思路的作用。

全局平衡二叉树

来讨论一下上面的第二种维护方式（并非真正的全局平衡二叉树）：

每条重链单独使用一个数据结构进行维护，其缺点是不方便子树修改，优点是每个重链的结构独立，有更大的调整空间，同时链修改的常数更小。我们需要额外算出每个节点在重链中的位置。

首先这种方法是可以卡到单次操作 O(\log^2 n) 的，比如下面这种树形：

（不过这里有一个很有趣的问题就是：每个点向根改一次，最坏情况下的复杂度是多少，这种情形出现在某些动态 DP 中，如 [ZJOI2019]Minimax搜索 中每个叶子会向根修改一次，如果有人能给出证明或给出构造请评论区指出或者私信我，不胜感激）

upd on 2023.12.13

from @YeahPotato, from myh in vuq

所谓“链式堆”的结构可以将这个问题卡到两只 \log，以下是这个结构更加详细的描述：

考虑一棵 \sqrt n 个点的完全二叉树（点对应图中的黑色点），每条边裂成 \sqrt n 点，同时每个点伸出 \sqrt n 个叶子。这样，每条重链长度都是 k\sqrt n，一个点更新的重链条数等于在原二叉树上根到它走的右儿子次数，平均也是 O(\log n) 的。

但是由于各个线段树的结构相互独立，因此能够从全局上进行调整，因此产生了全局平衡二叉树这种东西。

我们的目标是任意一个点到根路径上只经过 O(\log n) 个线段树节点，一种可行的方式是这样的：改变 mid 的选取方式，不再以区间中点作为 mid，而是一个节点赋上轻儿子 siz 之和的权值之后取带权中点。这样每个点向上跳一步，对应的子树大小翻倍，那么就只会经过 O(\log n) 个线段树节点了。

这里区间 [l,r] 的带权中点的定义为：

• 记 S 为区间中所有点的权值之和。

• 则带权中点 M=\min\left\{x\vert l\le x<r,l\sim x\text{的权值之和}\ge \frac{S}{2}\right\}，若不存在则定义为 r-1。

这样可以形成正常的广义线段树结构，线段树操作中除了 mid 变了，其他都不变，模板记忆起来也更方便一些。

全局平衡二叉树的一种实现方式：

int Find(int x, int y){
    int tot=(pre[y]-pre[x-1])/2,l=x,r=y-1,p=y-1;
    while (l<=r){
        int mid=(l+r)>>1;
        if (pre[mid]-pre[x-1]>=tot) p=mid,r=mid-1;
        else l=mid+1;
    }
    return p;
}
void build(int& now, int l, int r){
    now=++tsize;
    if (l==r) return tr1[now]=tr2[now]=Mat[seq[l]],void();
    Mid[now]=Find(l,r);
    build(ls[now],l,Mid[now]);
    build(rs[now],Mid[now]+1,r);
    pushup(now);
}
void dfs2(int u){
    for (int i=u,j=1; i; i=son[i],j++){
        seq[j]=i,pre[j]=pre[j-1]+siz[i]-siz[son[i]];
        vis[i]=1,top[i]=u,len[u]++;
    }
    build(rt[u],1,len[u]);
    for (int i=u; i; i=son[i])
        for (int v:G[i]) if (!vis[v]) dfs2(v);
}

我才不会告诉你这是我直接从我 CSP2022 T4 代码里截出来的

但是这种写法的常数还是较大的，据我所了解，一般的动态 DP 中的全局平衡二叉树并不会写成这个样子，而是会写成下面这种样子，也供参考，常见的动态 DP 实现形式，以 P4751 为例。

几个应用

[模板] 树链剖分

学习重链剖分之后必须要会的一些操作：

• 子树加/子树查和

• 树链加/树链查和

• 换根

这里简单提一下换根，这是 ds 题中可能会遇到的一个操作：

• 换根对树链修改查询没有影响，因为不管根怎么变，树链还是那条树链，上面的节点不会改变。

• 换根对子树修改查询有影响，需要分情况讨论一下：

设目前树根为 r，则节点 u 的子树为：

1. 以 1 为根的情况下，u 为 r 的祖先，这种情况下，取 u\sim r 链上 u 的儿子 v，则 u 子树为全局去掉以 1 为根下 v 的子树。

3. 其他情况，以 r 为根下 u 的子树与以 1 为根下 u 的子树相同。

分类讨论了之后，就可以只利用以 1 为根的 dfn 序列来支持换根之后的子树范围定位了。

这里节点 1 是任意取的，可以是其他的任何一个节点。

处理重链之间的影响

点有颜色

• 子树/树链颜色覆盖

• 树链颜色段数

例题为 [NOI2021] 轻重边

动态 DP

对于一类特殊的 dp，我们可以写成某种具有结合律的广义矩阵乘法的形式，那么它们就能够在序列上动态修改，快速维护。

[CSP-S 2022] 数据传输，k=2，序列上的弱化版

有一个序列，每个点有点权 a[i]，每次可以往后跳一步或两步，每到一个点产生该点点权的代价，问起点到终点的最小代价。

有一个简单的 dp：dp[i] 表示起点开始到 i 的最小代价，有转移 dp[i]=\min(dp[i-1],dp[i-2])+a[i].

写成 (\min,+) 矩阵乘法，就是：

\begin{aligned} dp[i]&=\min(dp[i-1]+a[i],dp[i-2]+a[i]) \\ dp[i-1]&=\min(dp[i-1]+\ \ 0\ \ ,dp[i-2]+\ \infty\ ) \end{aligned} \begin{bmatrix} dp[i]\\ dp[i-1] \end{bmatrix} = \begin{bmatrix} a[i]\ \ a[i]\\ 0\ \ \ \ \ \infty \end{bmatrix} \begin{bmatrix} dp[i-1]\\ dp[i-2] \end{bmatrix} 这个东西还可以上树（~~上仙人掌~~）：每次询问一条树链，把这条树链抽出来当做序列进行查询。 这个也是没有问题的，相当于树上每个节点具有一个矩阵，然后把所有树链上的矩阵按一个方向乘起来即可，这个东西显然是可以用重链剖分解决的，并且还是可以带修。注意矩乘没有交换律，因此重链上需要维护两个方向的矩阵乘积。 **但这其实不算真正的树上动态 dp，因为它的本质还是序列 dp。** 真正的树上动态 dp 是长这样的： > 给出一棵树，点有点权，动态修改点权，查询最大权独立集。 考虑朴素的树形 dp：$dp[u][0/1]$ 表示 $u$ 子树，$u$ 选或不选的最大权独立集，那么转移： $$ \begin{aligned} dp[u][0]&=\sum_v\max(dp[v][0],dp[v][1]) \\ dp[u][1]&=\sum_vdp[v][0]+a[u] \end{aligned} $$ 选出一个 preferred-son 为 $x$，分离其他儿子： $$ \begin{aligned} f[u]&=\sum_{v\not=x}\max(dp[v][0],dp[v][1]) \\ g[u]&=\sum_{v\not=x}dp[v][0]+a[u]\\ dp[u][0]&=\max(dp[x][0],dp[x][1])+f[u]\\ dp[u][1]&=dp[x][0]+g[u] \end{aligned} $$ 写成 $(\max,+)$ 广义矩阵乘法，即： $$ \begin{aligned} dp[u][0]&=\max(dp[x][0]+f[u],dp[x][1]+\ f[u]\ \ )\\ dp[u][1]&=\max(dp[x][0]+g[u],dp[x][1]+(-\infty)) \end{aligned} $$ $$ \begin{bmatrix} dp[u][0]\\ dp[u][1] \end{bmatrix} = \begin{bmatrix} f[u]\ \ f[u]\\ g[u]\ -\infty \end{bmatrix} \begin{bmatrix} dp[x][0]\\ dp[x][1] \end{bmatrix} $$ 这有什么用呢？我们发现了如下几个事情： - 一个点的点权修改之后，只有到根路径上的 dp 值会改变。 - 由 preferred-son 剖分出的每一条重链上，有比较好的快速维护方式。 因此考虑重链剖分，因为每个点修改之后，到根路径上只有 $O(\log n)$ 条重链受到影响，每一条重链可以暴力更新，于是大致的流程是这样的： ``` modify(p): while (p){ 求出 p 所在重链的 dp 值（此时 p 处的矩阵已经被改了，但没有 update 过，因此求出的 dp 还是原先的） 把 p 所在重链的 dp 值对更上面一条重链的影响消除（如上面的 f,g 值） 更新 p 这个位置 再求出 p 所在重链的 dp 值（这时的 dp 值是正确的），更新更上面的重链 p=fa[top[p]]（跳上去） } ``` 动态 dp 统一的思路就是轻子树的结果合起来当常数项，通常使用全局平衡二叉树实现（加上矩乘完全展开）（矩乘比较慢）。 例题： - [[NOIP2018] 保卫王国](https://www.luogu.com.cn/problem/P5024) - [[ZJOI2019] Minimax搜索](https://www.luogu.com.cn/problem/P5281) - [[ZJOI2022] 深搜](https://www.luogu.com.cn/problem/P8334) 挂一份自己的 [[ZJOI2022] 深搜](https://www.luogu.com.cn/problem/P8334) 的 [全局平衡二叉树代码](https://www.luogu.com.cn/paste/ky8371wz)。 #### dsu on tree 这只是一类思想，继承 preferred-son 的信息，暴力遍历其他轻儿子的信息（即树上启发式合并）。在重链剖分，长链剖分中都可以使用，在长剖中一般解决子树 dep 有关的问题，在重剖中的应用会更广，比如子树数颜色。 但是好像线段树合并的功能完爆它？（除了空间多个 log） 例题： [[THUSC 2021] 白兰地厅的西瓜](https://www.luogu.com.cn/problem/P10241) 还有另一方面的用法，就是统计树上所有点对的信息（实际上也可以点分治/边分治），比如下面这题： [CF914E Palindromes in a Tree](https://www.luogu.com.cn/problem/CF914E)： > 一个点有 `a` 至 `t` 的一个字符，称一条路径合法当且仅当其中所有节点上的字符通过重排可以得到一个回文串，对每个点求出经过它的合法路径数。$2\le n\le 2\times 10^5

首先一条路径合法当且仅当至多一种字符在路径中出现的次数为奇数次。记出 a[u] 表示 u 这个点的值 2^{ch[u]}，val[u] 表示 1 至 u 链上字符奇偶性的 bitmask，那么 u,v 链合法当且仅当 \operatorname{popcnt}(val[u]\oplus val[v]\oplus a[LCA(u,v)])\le 1。

需要对所有这样的点对进行统计。

由于需要对每个点求出经过它的合法路径数，一个显然的思路是这样的：对一个合法路径 u\rightarrow v，这条路径上的点的答案加一。通过树上差分我们可以发现只需要改变 u,v,LCA(u,v),fa[LCA(u,v)] 这 4 个位置的差分值。

考虑 dsu on tree，对一个点求出它作为 u,v 以及 LCA(u,v),fa[LCA(u,v)] 的次数，暴力枚举轻子树中的节点 p 进行统计，同时需要支持一部分节点中 val 为某个数的所有点差分值加一，记一个整体增量，实现起来有一些细节，不在此赘述。

上述 dsu 的一个实现

dsu 的一个优点在于通常情况下它的常数还是比较小的（除了类完全二叉树的结构），在上面这题中，它估计还比标算的点分治好写一点。

链分治（静态/动态）

链分治的思路是这样的：对当前子树（初始为整棵树），提出根所在的重链，删去链上的所有点，形成若干棵子树，对每棵子树分别递归求解，再把返回上来的信息合并到对应重链上的位置，以序列的方式合并重链上的信息。

以树形 dp 为例，一般来说，重链上计算的顺序是由深至浅的，但在一些有结合律的问题中，合并的速度往往能更快。

上面的图是一个例子，下面的图是由链分治形成的结构，暂且称之为“链分树”（本人 Graphviz 水平有限，画不出精美的图片）。

链分树的树高为 O(\log n)，节点数为 O(n)，每个节点对应原树中的一条重链，其信息为原树中重链链顶节点的子树信息。

链分树中一个节点的信息可以由其儿子的信息和所对应重链中节点的信息通过序列的方式合并出来。

这样的过程，不涉及到动态修改，就称为静态链分治。

同时，改动一个节点的信息，只会有 O(\log n) 个链分树上节点的信息发生变化，如果信息的合并可以在序列上支持快速带修，那么就能够在树上做，动态 dp 就是一个经典的例子，这也是它被称为“动态链分治”的原因。

例题：

给出一棵 n 个点的树，边有边权。

对每个 k\in [0,n)，求出在树中选出 k 条节点端点互不相同的边，边权和的最大值。

好像是一个广为人知题。

正常的 dp：记 dp[u][0/1][i] 表示 u 子树中，u 有没有作为一条选中的边的端点，选了 i 条边的答案。显然 dp 的合并是一个树上背包，因此可以 O(n^2) 暴力。

考虑优化这个暴力，经过打表可以发现，dp[u][0/1][i] 是上凸的，同时 dp 的合并与闵可夫斯基和的形式相同，因此直接使用凸包的闵可夫斯基和，单次合并做到 O(siz_a+siz_b)（原先是 O(siz_a\times siz_b）)

然后考虑链的情况，对一个分治区间 [l,r]，编号为 u，记 f[u][i][0/1][0/1] 表示这个区间中取了 i 条边，左右端点分别有没有取的最大值。在合并的时候只需要分 mid\sim mid+1 这条边有没有取进行一下讨论。利用上面凸壳的性质进行合并，可以做到 O(n\log n)。（可以这么干是因为凸包的闵可夫斯基和具有结合律）

然后扩展到树上，直接使用静态链分治的结构：

剖出一个重链来，对重链上的每个节点，我们需要求出其所有轻儿子的 dp 信息和，准确来说，要求出 g[u][0/1][i] 表示 u 点以及其轻儿子中取 i 条边，u 有没有取的答案。那么有 f[u][0][0][]=g[u][0][],f[u][1][1]=g[u][1][]，但是思考一下之后发现这个似乎没有简单的合并方法，只能再次使用分治：

对一个节点的所有轻儿子分治：对一个分治区间 [l,r]，编号为 u，记 g[u][0/1][i] 表示对该区间内的轻儿子，其中取 i 条边，u 有没有取的答案，然后分治合并是显然的。

总的时间复杂度 O(n\log^2n)。参考实现方式

例题：[ABC269Ex] Antichain

一些非经典应用

例如 Nauuo and Binary Tree，OI-wiki 已经有较为详细的解释了，这里不再重复说明（照搬照抄）。

长链剖分

出于习惯会把剖出的链称为长链，但轻/重儿子（边）的描述方式仍然不变。

这种剖分方式也有一些性质：

• 任意节点到根路径上轻边的数量为 O(\sqrt{n})。

• 一个点 u 的 k 级祖先所在长链的长度 \ge k。

长链剖分的性质没有重链剖分好，因而功能也没有重链剖分多。但在处理一些子树深度问题的时候，长链剖分具有更优的复杂度。

几个应用

快速求 k 级祖先

长链剖分可以做到 O(n\log n)\sim O(1) 在线回答 k 级祖先。

1. 先预处理出每个点的 2^i 级祖先，可以用倍增实现。

2. 对每条长链，求出链顶向上链长个祖先，存下来。

3. 对查询的 u,k，记 k=2^p+l(0\le l<2^p)，先从 u 跳到 u 的 2^p 级祖先处，由上面的性质，此时所在长链的长度 \ge 2^p>l，那么再根据预处理的信息以及 l 来选择合适深度的祖先即可。

大致知道做法就行，这种东西基本不考

ds 方面？

由于一个点到根路径上轻边的数量为 O(\sqrt n)，我们并不指望长链剖分在数据结构问题上有出色的表现。

因此并没有 ds 方面的应用。

dsu on tree

一类思想，继承重儿子的信息，暴力合并轻儿子的信息。

长链剖分在处理子树深度问题时往往会有奇效，因为重链剖分的 dsu on tree 总共的合并次数是 O(n\log n) 的，而长链剖分在按 dep 合并时总共的合并次数是 O(n) 的（因为一条长链会在链顶处贡献链长的合并次数），两者的本质区别是处理子树 dep 问题时认为 dep 相同的所有点的信息能够合并，所以在这种特定的问题下长剖 dsu 更优，而重剖 dsu 保留了所有节点的信息，因而更差一些。

大致可以分成两类问题：

节点深度的统计问题

CF893F Subtree Minimum Query 加强

给出一棵以 1 为根的树，点有点权，q 次询问一个点子树中，dep 在一段区间内的点权 \min，强制在线。

1\le n,q\le 10^5

记 dp[u][i] 表示 u 子树中，与 u 的距离为 i 的所有点的点权 \min，那么对于重儿子：

dp[u][i]=dp[son[u]][i-1](i\ge 1)

对于轻儿子，暴力遍历它的 dp 数组进行更新，这样复杂度是 O(n) 的。

考虑到继承和空间问题，一般需要动态开空间，这个并不方便，我们希望能把所有 dp 信息固定在一起。

使用 dfn 序列就可以完成这个任务，预处理 dfn 序列，把 dp[u][i] 记到 dfn[u]+i 这个位置上，由于每条长链在 dfn 上按节点顺序是一段区间，这样可以方便地继承，并且取出任意位置的 dp 值了。

void dfs(int u, int f){
    for (int v:G[u])
        if (v!=f) dfs(v,u);
    for (int v:G[u])
        if (v!=f && v!=son[u])
            for (int i=0; i<=mxdep[u]; i++)
                把 dp[dfn[v]+i] 合并至 dp[dfn[u]+i+1]
    将 u 本身的信息记入 dp[dfn[u]]
}

固定到 dfn 序列上之后，我们还可以用数据结构来干一些事情，比如这个题要维护深度在一段区间内的点权 \min，那么对 dfn 序列建立线段树，就是一个单点修改，区间查询了。

然后强制在线也没有问题，由于长剖的性质，单点修改只有 O(n) 次，因此对每个时刻把线段树的信息可持久化出来是没问题的。记录每个点在 dfs 完的版本编号，查询的时候就可以直接查了。（类似的思想在可持久化线段树合并里也有）

void dfs(int u, int f){
    for (int v:G[u])
        if (v!=f) dfs(v,u);
    for (int v:G[u])
        if (v!=f && v!=son[u])
            for (int i=0; i<=mxdep[u]; i++)
                新建一个版本，把 dp[dfn[v]+i] 合并至 dp[dfn[u]+i+1]
    新建一个版本，将 u 本身的信息记入 dp[dfn[u]]
    记录此时的版本编号以供之后查询
}

一份上述方法的实现

与节点距离有关的统计问题

这类问题的统一思想是这样的：

• 同一 dep 的所有节点的信息可以合并，同时处理。

• 每个点继承重儿子的信息，所有树链分为直链和弯链查询，弯链枚举轻儿子那边，统计另一边，直链直接统计。

给出一棵树，边权均为 1，问其中距离为 k 的点对个数。

使用长链剖分，记 dp[u][i] 表示 u 子树中，与 u 的距离为 i 的节点个数，直链的答案显然是 \sum dp[u][k]。

对于弯链，完成以下过程即可：

先继承重儿子信息，接下来依次加入轻儿子 v，进行：

ans+=\sum_{i=0}^{mxdep[v]} dp[v][i]\times dp[u][k-i-1] dp[u][i+1]+=dp[v][i](0\le i\le mxdep[v])

依然是可以把 dp 压到 dfn 上。

[WC2010]重建计划 转化后的题意

给出一棵树，边有正负边权 ，求一条长度在 [L,R] 内的最大权树链。

记 dp[u][i] 表示 u 子树中，一段在 u，另一端与 u 的距离为 i 的最大权树链。

在短链合并到长链的时候，使用 dfn 序列加上线段树维护区间 \max 即可。

合并的时候分直链和弯链讨论一下，具体方法与上面的相同，比点分治加单调队列好写了不少。

参考实现

例题：CF1712F Triameter