自动搬运

查看原文

来自洛谷，原作者为

	FutaRimeWoawaSete Dear the f**king destiny!

搬运于2025-08-24 22:36:54，当前版本为作者最后更新于2022-03-27 18:54:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

你卡树上倍增 LCA！！！

为什么卡为什么卡为什么卡！！！我卡了一个下午常也没想到是这里被卡常了！！！

基于树上祖先-子孙链询问的二次离线莫队。

考虑套路地将边权转点权，问题变成了多次查询在虚树上的点与在虚树上的祖先的顺序对数量。

考虑区间逆/顺序对最常用的一个方法：二次离线莫队。我们只需要做到将询问的东西拆成很多条链上答案的组合，求出所有链询问的答案即可。

联想到建立出的所有虚树的点的数量级仍为 $O(\sum t_i)$，我们想到拆成数量级有关树点数的若干区间逆序对：

记 $s(l,r)$ 为 $l$ 作为祖先，$r$ 作为子孙，刨去祖先 $l$ 后原树链上的点与 $r$ 构成的逆序对数量，$T$ 为当前构建的虚树，$rt$ 为当前虚树的祖先。

则答案为：

$\sum_{i \in T} s(rt,i)$

记 $ps(l,r)$ 为 $l$ 作为祖先，$r$ 作为子孙，刨去祖先 $l$ 后原树链上的点构成的逆序对数量，$d(x)$ 为点 $x$ 在虚树上的儿子数。

那么答案可以被差分成：

$\sum_{r \in T,r \in Leaf} ps(rt,r) - \sum_{i\in T,i \notin Leaf} (d(i) - 1) \times ps(rt,i)$

就算不从容斥的角度，这个差分也很好理解。可以考虑自底向上，儿子们每处理完自己需要差分的东西后，儿子所属的子树对于父亲差分系数的贡献只剩下 $1$，由于自己本身要贡献一次，所以当前的差分系数是 $(d(i) - 1)$。

接着问题变成了对于 $m = 2 \times 10 ^ 6$ 数量级的树上区间逆序对询问。可以考虑使用 dfs 序，在 $st_x$ 处记为加入一个点（正贡献），$ed_x$ 处记为删除一个点（负贡献）进行二次离线莫队。

这里这么做的正确性是考虑到所有的询问都是祖先-子孙链，所以 $st_x$ 一定是加入一个点，$ed_x$ 一定是删除一个点。

同时要注意左右端点移动到底是找小于端点值的数还是大于端点值的数，建虚树时要特判根节点 $1$ 是不是虚树的实际根，要对根节点 $1$ 的所有查询都手动返回 $0$，不要用 dfs 搜虚树（这个视情况，是卡常点），不要开小数组，不要写树上倍增求 LCA，要写树剖求 LCA，否则至少要被卡 0.5s。

大概就这些了。

时间复杂度 $O(n \sqrt m)$，但是个人写出来莫队的部分用时还不一定比建虚树部分用时多。

此题存在一种基于树分块的二次离线莫队实现，貌似常数要小一些。