长链剖分
foreverlasting
·
·
个人记录
长链剖分是一个好用的东西。
众所周知的树链剖分都是重链剖分，但长链剖分身为一种特殊的树链剖分其实有着巨大的应用（事实上市场上用长链剖分的题并不多）
那什么是长链剖分？
我们知道，重链剖分是根据子树大小来判断重儿子以及重链，而长链剖分则是根据点的深度来判断长儿子（？）以及长链。
像重链剖分一样，我们定义点x的长链指从点x出发，到达其最深的后代所经过的路径。那么长儿子就是长链上的儿子。
于是我们可以通过长链，把一棵树剖成若干条不相交的路径。
长链剖分有两个重要性质：
这是显然的。
$2$、任意一个点$x$的$k$级祖先$y$所在长链长度一定大于等于$k$。
这点我们分类讨论$x$和$y$是否在同一条长链上就能轻松证明了。
通过这两个性质，我们就能做很多事情了。
比较经典的例题就是：给你一棵树，多次询问$x$，求$x$的第$k$级祖先。
这个该如何运用长链剖分呢？
我们可以这样处理：
首先，对树进行长链剖分，记录链头和链尾，同时处理倍增数组，这里复杂度是$O(nlogn)$。
如果某条长链的长度是$L$，那么在链头处记录链头向上的$L$个祖先，并记录向下的$L$个链的元素
同时预处理出$1$到$n$每个数二进制表示最高位的$1$，时间复杂度$O(n)$。
接下来就是询问。
对于每一个点的$k$级祖先，我们可以进行如下操作。
$1$、先利用倍增数组跳$k$的最高位的$1$层，设剩余层数为$k'$，可以发现$k'<\frac{k}{2}
于是我们就做到了$O(nlogn)$预处理，$O(1)$询问。
长链剖分还有一种对于$DP$的优化，就像[这道题](https://www.luogu.org/problemnew/show/P3565)，bzoj上有加强版，那里就必须要长链剖分处理了。凭什么这道题能用长链剖分？这是因为这道题的$DP$只与深度有关，所以对于长链上我们可以直接$O(1)$转移，不同长链暴力转移。因为性质1，所以这样的均摊复杂度会降到$O(1)$，那就能降一个n的复杂度下来。
下面给出几道例题：
[【POI2014】HOT加强版](https://www.lydsy.com/JudgeOnline/problem.php?id=4543) [题解](https://www.luogu.org/blog/foreverlasting/poi2014hot-hotels)
[【WC2010】重建计划](https://www.luogu.org/problemnew/show/P4292) [题解](https://www.luogu.org/blog/foreverlasting/wc2010-zhong-jian-ji-hua)
[【湖南集训】谈笑风生](https://www.luogu.org/problemnew/show/P3899) [题解](https://www.luogu.org/blog/foreverlasting/solution-p3899)