P12038 题解

· · 题解

考虑对于 $x$ 子树，求出包含 $x$ 的最优解。 先对 $x$ 子树剖 $x$ 所在的重链，对挂在重链上的轻子树全部暴力求解。钦定选取的 $x$ 重链前缀，将轻子树划分到两个集合，使得两个集合内总点数 $\le\frac{siz_x}{2}$，然后折半合并出最优解，这是经典问题。 考虑证明总能分两个合法集合。设重链长度为 $len$，构造一个序列 $a$ 表示所有挂在 $x$ 重链上的轻子树大小，然后往 $a$ 中加入 $len$ 个 $1$。将 $a$ 从大到小排序，试证明 $a_x\le\sum_{x\lt y}a_y$（可能有点不严谨）：在重链上找到最低的 $u$ 使得 $siz_u\lt x$，$siz_{par_u}\ge x$，$par_u$ 的轻子树 $siz\le siz_u\lt x$，选取 $par_u$ 子树内所有 $a$ 即可。然后从大到小依次考虑 $a$，由于 $a_x\le\sum_{x\lt y}a_y$ 且 $\sum a=siz_x$，所以你总是能将 $a_x$ 扔进较小的集合。 算完包含 $x$ 的最优解直接递归算所有子树即可。 复杂度 $\sum{2^{\frac{siz_x}{2}}siz_x^2}$ 即 $O(2^\frac{n}{2}n^2)$（因为有排序），能优化到 $O(2^\frac{n}{2}n)$，人傻常数大，跑得比 $O(2^{\frac{3n}{2}}n)$ 慢。