Searching For Hope (hard) 题解

· · 题解

算法 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。