如何高效的用链剖分打出模板题的暴力

· · 休闲·娱乐

就是我们发现了一道模板题。

然后我们想把他做出来，于是你打了个 O(n^2) 的暴力，它 T 了。

但是，我们知道一个算法叫做长链剖分，它可以对树进行剖分，这样就可以将一棵树转化为序列。

它的思路为每次找到一个节点深度最深的儿子，将这条边设为标记边。

由多条标记所构成的链就可以形成很多个序列，这也很方便我们去查询。

这种链剖分的思路是一个非常强的思路，因为它将困难的树上问题转化为了一个简单的我们会做的序列问题。

因为一条树链是多条标记链所构成的。

那么子树怎么做呢？我们发现，一个子树的 dfs 序是连续的，所以这就可以利用 dfs 序搞到序列上了。

但是我们想一件事情，如何将链上的修改的贡献放到子树的查询上呢。

于是我们想要做一件事情，就是如何使一条链上的 dfs 序连续。

可以考虑 dp，就是设 dp_{i,j} 是 i 的 dfs 序为 j 是否有构造方案。

然后 dp 方程让大家自己想吧，大体思路就是需要使 j+1 被分配到标记的儿子上，其他节点随便分配。

然后逆推即可得出 dfs 序的方案，接着我们可以考虑用数据结构维护了。

这边我们为了追求简洁高效常数小，线段树，平衡树，LCT 这种数据结构就可以淘汰了。

于是我们选择了分块维护。

现在我们来证明时间复杂度：

性质 1：这种剖分方法链尾一定是叶子。

证明：如果不是叶子，与每个不是叶子的点都有一个标记儿子。

性质 2：我们发现每次向上跳标记链的长度是单调不降的。

证明：

。

如果 l_1<l_2，那么一定会去剖橙色部分。

而我们跳了 k 条链，那么这就出现了长度总和至少为 \dfrac{k(k+1)}{2} 的链，而链不重合。

所以 k 最多为 O(\sqrt{n})。

所以跳到根节点最多会有 O(\sqrt{n}) 条链。

此时加上分块的复杂度，这就是 O(n^2) 的。

然后 dp 转移显然是 O(1) 的，所以这个 dp 是 O(n^2) 的。

你成功打出了一个优雅的暴力。