自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:53:40，当前版本为作者最后更新于2023-12-25 22:46:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先进行 top cluster 树分块。考虑这样一件事，对于两个簇的底部界点 $(u,v)$，我们把两个点都在 $u,Fa_u;v,Fa_v$ 界点路径上的询问全都拉出来一起做，那么每次变化量肯定不会超过 $4\sqrt{n}$。

接下来要解决的只剩 $(u,v)$ 转移到下一个 $(u,v)$ 的代价和了，我们考虑抛出以下做法。

设 $siz_u$ 为子树内界点个数和。对于 $(u,v)$，设 $u$ 子树内界点 $siz$ 最大的为 $x$，$v$ 子树中的为 $y$，若 $siz_u-siz_x<siz_v-siz_y$ 则 $(u,v)$ 从 $(x,v)$ 转移过来，否则从 $(u,y)$ 转移过来。

这样子状态之间转移构成了一个大小为 $n$ 的森林，在每棵树上遍历一遍即可。我们声称这样做时间复杂度是 $O(n\sqrt{n})$ 的。

这是因为在 $n$ 个点的树上轻子树大小和 $\geq x$ 的点的个数是 $\frac{n}{x}$ 级别的，因为考虑在叶子处挂上这些 $x$ 合并上来，只会合并叶子个数 $-1$ 次。

那么考虑枚举 $x$ 算贡献，一对 $(u,v)$ 在 $x$ 有贡献当且仅当轻子树大小和的 min 大于等于 $x$，那么对于 $x$ 来说，可能产生贡献的界点点对数量最多为 $(\frac{\sqrt{n}}{x})^2$。那么答案的级别算一下就是 $\sum_{x=1}^{\sqrt{n}} \frac{n\sqrt{n}}{x^2}\rightarrow n\sqrt{n}$。