你说得对，但是你知道这是原吗

NATO · 2024-07-01 20:49:52 · 题解

写在前面：

这是不久前笔者与以前的同学胡的一个对于单次询问形如 \sum\limits_{i=l1}^{r1}\sum\limits_{j=l2}^{r2}val(lca(id_i,id_j)) 的通用在线 O(q\sqrt n+n\sqrt n) 解法，其中 id 是一个预先给定的对应点编号的任意序列，val(lca(id_i,id_j)) 是一个只与 lca(id_i,id_j),id_i,id_j 有关的一个值。

本做法的优势在于不需要使用任何除了“val(lca(id_i,id_j)) 是 lca(id_i,id_j) 的 val”以外与 val(lca(id_i,id_j)) 相关的任何性质，普遍性很强，且不需要进行任何化简，思维上简单粗暴。

后发现在一些题中均有类似解法，但写得没有那么清晰。遂决定在此作文以较为详细地介绍此类解法。

要充分理解此文，您可能需要的前置知识：

分块、常见换根 DP 的用法、任意方法实现的 O(1) 查询 LCA、单调栈建虚树。

思路浅析：

让我们从另外一道题谈起。

P4211，这道题题解区中的第三篇题解提出了一种不同于一般 O(n \log n^2) 的 O(n\sqrt n) 的解法。

其解法即是按编号分块，每次将一个块中的节点标记，然后遍历一遍树，预处理出每个节点子树内被标记的点的数量（下称 i 点子树内被标记的点的数量为 size_i），再做一遍换根 DP，预处理出 i\in\{1,2,...,n\},\sum\limits_{j=l}^{r}val(lca(i,id_j)) 的值（在上题中即是 \sum\limits_{j=l}^{r}dep(lca(i,j)) 的值，其中 l,r 指一个块的边界），再对每个点存的块的答案做一遍前缀和。

具体解释一下上文的换根 DP，当我们换到一个节点 k 时，我们此时即是在求出 \sum\limits_{j=l}^{r}val(lca(k,id_j)) 的值，我们将这个东西分作两个部分考虑：第一个部分就是在 k 子树内的所有被标记的点，这个部分的 LCA 就是 k 点本身，是容易统计的；第二个部分即 k 子树外的点，这个部分的答案可以在向下转移时传一个值进行记录，即从一个点 u 转移到 v，那么显然 u 子树内除了 v 子树内的标记点与 v 子树内任意一个点的 LCA 即是 u，那么给下传的值加上一个 (sz_u-sz_v)val(u) 即可。

对于一个询问 l,r,z，调用 z 对应的前缀和答案差分一下，求出 [l,r] 间的整块与 z 的答案，散块使用 O(1) 查询的 LCA 暴力查询即可。

总结一下上述过程，实际上我们就是通过分块和换根 DP 尽可能地在可接受的范围内预处理出尽可能多的答案，这样在询问时就可以对少数“边角料”用相对暴力的方法解决了。

上述即是对该题解内容的详细展开，为的是引出解决 \sum\limits_{i=l1}^{i=r1}\sum\limits_{j=l2}^{r2}val(lca(id_i,id_j)) 的解法（这难道不就是解法的绝大部分思路吗）。

现在让我们把视线回到 \sum\limits_{i=l1}^{i=r1}\sum\limits_{j=l2}^{r2}val(lca(id_i,id_j))。

我们发现，我们需要解决的问题的形式与 P4211 的形式只是多了一层求和罢了。考虑继续沿用分块的思路，整块对整块、整块对散块和散块对整块均可以很容易地用我们预处理的点对块的答案作前缀和后差分求得，这里不展开，相信读者若是明白了上文分块和换根 DP 在干什么的话是能够轻松实现的。

但是瓶颈在于散块对散块的贡献，我们发现用预处理的答案是无法解决的，而暴力枚举点对的做法显然是会使单次询问复杂度退化为 O(n) 的，该怎么办呢？

我们先不谈分块，回顾一下刚才的换根 DP，我们还可以发现一种 O(nq) 的做法，即将 [l2,r2] 的点标记一下，再像分块预处理那样做换根 DP，在树上 [l1,r1] 的位置统计答案即可。

让我们仔细考虑这个过程，容易发现只有在 [l2,r2] 两两间 LCA 是可能导致换根记录的答案发生变化的。emm...只有关键点和其 LCA 有用，这不是暗示我们建虚树吗！

（下设 len 为 [l1,r1],[l2,r2] 区间总长度）于是我们将 [l1,r1],[l2,r2] 的点建虚树后再跑换根（这里假设可以 O(len) 建虚树），复杂度单次就变为了 O(len) 的！

回到我们要解决的散块对散块，我们发现只要能 O(len) 建虚树问题就解决了，毕竟当块大小为 O(\sqrt n) 时，散块中数的个数是 O(\sqrt n) 的嘛。

翻阅 OI Wiki 可以得知我们知道一种按 dfs 序排序后使用单调栈建虚树的方法，但排序仍然是 O(len\log len)。尝试利用我们的分块来优化排序的过程，考虑对块内按 dfs 序排序，询问时对着四个散块排序后对应的块扫一遍合并即可完成排序的工作，然后用单调栈的做法就可以愉快地在 O(len) 的复杂度内建虚树啦（温馨提示：您的常数已上天）。

然后和上文预处理时类似地跑个换根 DP 统计贡献即可。

至此，我们就完成了散块对散块这一瓶颈，于是当块长取到 O(\sqrt n) 时整个问题便可以以 O(n\sqrt n) 的时间复杂度解决了。

不过这个玩意有着显而易见的缺点：

1. 如果块长取到 O(\sqrt n) 的话，不逐块处理空间复杂度同样高达 O(n\sqrt n)。

2. 代码难度极高，很容易写错。

3. 常数巨大，以致于可能跑起来比 O(n\sqrt n\log n) 还慢。

4. 容易被某些情况下存在的 \text{polylog} 做法乱杀。

综上所述，本做法就是彻彻底底的小丑做法，建议立刻枪决笔者。

好啦，让我们回过头来看看这篇文章投的题目该怎么做吧，写出形式化题面，即：

规定 id_1=1，给出 id_2,id_3,...,id_{m+1} 的值，对于 r=2,3,...,m+1 分别求出下式的值：

我们发现中间不是我们想要的 val(lca(id_i,id_j)) 的形式，简单拆一拆即可：