题解：P6847 [CEOI 2019] Magic Tree

AC_love · 2025-03-29 13:01:04 · 题解

设 f(i, j) 表示 i 的子树在第 j 天前被全部割掉的最大收益，考虑 i 位置的果实贡献。

如果不收割 i 位置的果实，有 f(i, j) = \sum_{x \in son_i} f(x, j)。

如果收割 i 位置的果实，有 f(i, j) = w + \sum_{x \in son_i} f(x, d)。

二者取 \max 即可。

暴力转移，复杂度 O(nk)，考虑优化。

考虑线段树合并。

发现收割 i 位置的果实时，这个贡献一定是个定值，计算出这个定值，令其为 x，扔到线段树上做区间推平下界。

区间推平下界的具体做法是：维护每个区间的 \min 和 \max。暴力 + 剪枝，当 \max 小于等于 x 时整块修改，当 \min 大于等于 x 时不用修改。这是个比较老套的套路了，复杂度是正确的。

加法操作的标记很难下传，标记永久化即可。