长链剖分学习笔记

树链剖分家族有两姐妹，一个叫重链剖分，一个叫长链剖分 我们说树剖，一般指重链剖分。而我在本博客里，会讲讲长链剖分 由于一些原因，对于重链剖分和长链剖分的相似部分本人会略过 所以看本文前，建议先学习重链剖分 ## 一、什么是长链剖分 长链剖分和重链剖分一样，是把一棵树分成若干条不相交的链。 但是，这里的重儿子不再是子树大小最大的，而是深度最大的子节点。（我们这里叫长儿子） 我们定义一个节点的深度，为这个这个节点的到这个节点的子树中的任意节点的路径经过节点数的最大值。 这样，我们就可以类似重链剖分的方式，把树分成了若干条不相交的链。 举个例子： 下面这棵树， 绿色的边就是长链  我们定义一个节点和它的长儿子节点相连的边（就是上图绿色的边）为实边，其他为虚边 对于一条长链 我们定义链顶为一条链顶为这条链深度最大的节点 定义链底为一条链顶为这条链深度最小的节点 剖分的代码和重链剖分类似 ``` //dep[x] 指x的深度 //zson[x] 表示 x 的长儿子 void dfs(int x) { int maxdep = 0; dep[x] = 1; for(int i = t[x]; i != 0; i = b[i].ls) { int y = b[i].y; if(y != fa[x]) { fa[y] = x; dfs(y); if(dep[y] > maxdep) { maxdep = dep[y];//感谢KonjAC_Lucas指出这个锅 zson[x] = y; } dep[x] = max(dep[x],dep[y]+1); } } } ``` ## 二、长链剖分的一些性质 #### 1、一个节点到它所在的长链的链底部的路径，为从这个节点到它子树每个子树所有节点的路径中，最长的一条。 #### 2、一个节点到根的路径，最多经过$O(\sqrt{n})$个虚边 证明： 对于一个节点，深度为$k$,则它往上跳一个虚边，则跳完后的子树大小，会加上至少$k+1$个点。（不然无法形成长链） 那么如果我们跳了x条虚边，此时树的大小，最少为 $\sum_{i=1}^xi = \frac{x(x+1)}{2}$个节点 所有一个节点到根的路径，最多经过$O(\sqrt{n})$个虚边 和重链剖分一样，这个$sqrt(n)$一般不满 ## 三、长链剖分的一些应用： #### 1.多次询问求树上节点的$k$级祖先 看到这里，我们会想到用倍增求，时间复杂度 $O(nlogn+qlogn)$ 当然也会有人说，可以离线下来，然后dfs遍历整棵树，在遍历到每个节点的时候存一下它到根节点路径的所有节点就可以了。时间复杂度$O(n+q)$ 然而，还有更好的做法吗？ 没错，就是长链剖分 长链剖分可以做到$O(nlogn)$预处理，单次查询$O(1)$的时间复杂度，**在线**处理这个问题 首先我们知道一个性质 任意一个点的k级祖先所在链的链长一定大于等于k。 证明很简单，这个点k级祖先所在的链长度肯定大于等于它到这个节点。 我们先倍增出每个节点的$2^t$级祖先。 然后，我们对于每条链处理。如果链长是$len$，那么在链头处记录链头向上的$len$个祖先，并记录向下的$len$个在链内的节点。 对于每次询问 我们设 $w = \lfloor log _2k\rfloor$ 然后，我们从利用倍增数组，从$x$跳到它的$2^w$级祖先，设$k' = k-2^w$(即我们还要跳$k'$层)。 此时，我们发现当前节点所在链 链长一定大于$k'$ 现在，如果这个节点的$k'$级祖先在它的链顶之下，那么可以用链顶向下的数组求出 如果在这个节点的$k'$级祖先在它的链顶之上，就用向上的数组求出 然后我们就可以$O(nlogn)$预处理,每次询问$O(1)$在线求$k$级祖先了。 [这里有一个模板题](https://www.luogu.com.cn/problem/P5903) #### 2.长链剖分优化dp 在学习这个之前，可以先学习一下[dsu on tree](https://pzy.blog.luogu.org/dsu-on-tree-xue-xi-bi-ji) 由于长链有很好性质，我们可以用来优化一些树上的dp。 一般来说，由于长链是一个点所在子树最长的链 所以这个性质可以很方便的维护一些信息 这样讲比较抽象，我们来一个具体的例子 [CF1009F](https://www.luogu.org/problem/CF1009F) 题意： 给出一棵有根树，对于每个节点$x$，定义一个无穷序列$d$，其中$d(x,i)$表示以$x$为根节点的子树中到$x$的距离恰好为$i$的点的个数，$i=0$~无穷，现在对每个点$x$，希望求出一个东西$j$，使得对于任意$k<j$，$d(x,k)<d(x,j)$，对于任意$k>j$,$d(x,k) \leq d(x,j)$ 树的点数 $\leq 10^6$ 其实就是求子树内深度的众数 首先我们想一个朴素的$dp$ $f_{i,j}$表示 节点$i$的子树内，到$i$点距离$j$的节点数量。（这里之前出了点锅，感谢installb的指出） 那么转移就是 $f_{i,0} = 1$ $f_{i,j} = \sum f_{son_i,j-1}$ 这是$n^2$的，不过可以用长链剖分优化 然后对于每个点，我们可以用该点所在的长链，向下$t_i$个点的位置，储存$f_{i,ti}$的信息 由于长链的性质，肯定是有地方存的 这样的话，对于每个节点的转移，长儿子的信息可以直接继承上去，其他儿子则暴力将它们所在的长链信息合并上去 由于每条链最多被合并一次 所以这样做就是$O(n)$的了。 这样讲讲可能比较抽象 我们来举一个例子  点里的数字是编号 点外地数字是我们维护的信息，我们定义这个值为$g_i$ 则答案就是 $j$在$i$的长链上的最大$g_j$ 现在除了节点1其他都已经维护好了 比如说$f_{2,1}$在这里就是$g_3$ 而2号点答案就是1 现在我们要维护$1$号点的信息 我们设置$g_1 = 1$ 然后，对于$1$的长儿子2，什么也不用做 对于$1$的其他儿子，合并上去 怎么合并？ 合并到对应高度即可  $6,7$号节点合并到箭头对应的结果 然后 $g_2$就变成了$2$ $g_3$就变成了$3$ 在合并的时候同时维护1所在链最大值 然后1的答案就是2了 [[湖南集训]谈笑风生](https://www.luogu.org/problem/P3899) 设 $\text T$ 为一棵有根树，我们做如下的定义： 设 $a$ 和 $b$ 为 $\text T$ 中的两个不同节点。如果 $a$ 是 $b$ 的祖先，那么称“$a$ 比 $b$ 不知道高明到哪里去了”。 设 $a$ 和 $b$ 为 $\text T$ 中的两个不同节点。如果 $a$ 与 $b$ 在树上的距离不超过某个给定常数 $x$，那么称“$a$ 与 $b$ 谈笑风生”。 给定一棵 $n$ 个节点的有根树 $\text T$，节点的编号为 $1$ 到 $n$，根节点为 $1$ 号节点。 你需要回答 $q$ 个询问，询问给定两个整数$p$ 和 $k$，问有多少个有序三元组 $(a,b,c)$ 满足： $a,b,c$ 为 $\text T $中三个不同的点，且 $a$ 为 $p$ 号节点； $a$ 和 $b$ 都比 $c$ 不知道高明到哪里去了； $a$ 和 $b$ 谈笑风生。这里谈笑风生中的常数为给定的 $k$。 这个主流做法是主席树，不过其实长链剖分也可以做，和上题做法类似。 设$s_x$为$x$为根的子树节点个数 考虑对于一个$a$，要么它是$b$的祖先，要么$b$的祖先有$a$ 我们分类讨论 当$b$是$a$祖先的时候，$c$点一定在$a$的子树内，$b$为a的不超过$k$级祖先，答案就是$min(h_a-1,k)*(s_a-1)$ 当$a$是$b$的祖先的时候，答案为$\sum_{ \text{a是b的祖先且}dis_{a,b} \leq k}s_b$ （之前有点锅，感谢Kinandra的指出） 这个用长链剖分维护一下即可，求出与a距离i的点的贡献，维护一下前缀和即可