自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:44:11，当前版本为作者最后更新于2023-01-24 21:14:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

算法 1-3

算法 4

使用启发式合并快速计算，对每一个点维护所有子树内的点当前的答案。

然后每次合并，小的子树全部 $\times 2$（暴力），大的子树部分 $\times 2$（暴力）部分整体加（打 tag），set 暴力实现为 $O(n\log^2n)$，期望得分 33。

算法 5

（感谢 E_Space 神仙！）

回到算法 3，考虑直接优化这个递推过程。

注意到，对于 $u$，如果 $f_u$ 的另一个子树（设为 $v$）满了，且 $f_{f_u}$ 的另一个子树（设为 $w$）的大小小于 $v$ 子树大小的两倍，则 $w$ 一定满了。于是我们可以把 $v$ 和 $w$ 缩起来。

具体来说，我们维护一棵辅助树 $T'$（记原树为 $T$），树上每一个点有一个二元组 $(l,s)$，代表触发这个点的另一个子树填满至少需要 $l$ 的大小，触发以后填满的所有子树大小总和为 $s$，将它向上第一个无法触发填满的点设为它在 $T'$ 上的父亲。

计算答案时，如果不能触发，则加倍，在 $T$ 上向上跳；否则在 $T'$ 上向上跳。考虑到每在 $T$ 上跳一次答案加倍，每在 $T'$ 上跳一次所在子树大小加倍，于是总复杂度 $O(n\log nc)$，期望得分 100。