P14637 [NOIP2025] 树的价值笔记

48 pts

类似 P15454。

考虑一个点 $u$ 不一定要立刻为 $mex$ 做贡献，可以往上走到若干层后对祖先 $fa$ 有 $mex$ 贡献，即在 $u$ 和 $fa$ 这一段中， $u$ 保持留空直到被 $fa$ 使用。

设 $f_{u, i, j}$ 表示考虑点 $u$ ，当前的 $mex = i$ ，还有 $j$ 个点未被使用的情况下，子树价值和最大值。

同样先考虑合并儿子，则有两种情况。

$i_{u}^{'}$ 继承 $i_{u}$ ，那么有 $f_{u, i, j_{1} + j_{2}}^{'} \leftarrow f_{u, i, j_{1}} + max_{i_{2} < i} f_{v, i_{2}, j_{2}}$ ，不能取等是因为取等会让 $i^{'}$ 增加。
$i_{u}^{'}$ 继承 $i_{v}$ ，那么有 $f_{u, i, j_{1} + j_{2}}^{'} \leftarrow max_{i_{1} < i} f_{u, i_{1}, j_{1}} + f_{v, i, j_{2}}$ 。

一维是前缀 $max$ ，一维是树形背包，可以做到 $O (n^{3})$ 。

接着考虑加入 $u$ 对答案的贡献，显然是 $f_{u, i, j}^{'} \leftarrow f_{u, i, j} + i$ 。

最后考虑使用垫脚石，即 $f_{u, i + 1, j - 1}^{'} \leftarrow max (f_{u, i + 1, j - 1}^{'}, f_{u, i, j} + 1)$

时间复杂度 $O (n^{3})$ ，空间复杂度 $O (n^{3})$ 。

考虑转换贡献，什么时候一个垫脚石是有用的？

考虑 $n^{3}$ 的 DP 机制，相当于每个节点 $u$ 选中一个儿子 $v$ ，继承其 $mex$ 值，并在整个 $u$ 子树内找垫脚石扩大自己的 $mex$ 。

接着， $u$ 的若干个祖先会继续继承 $u$ 的 $mex$ 值，而 $u$ 的其他儿子 $v^{'}$ 的 $mex$ 值在此时已经不再有用，也就是说垫脚石 $x$ 发挥的作用是给链 $1 \to x$ 中一段区间的 $mex$ 值 $+ 1$ 。

由于每个点都选择一个儿子继承 $mex$ ，这相当于一个链剖分，根据贪心，一定让 $x$ 贡献到 $1 \to x$ 中最长的一段链上。

因此可以用状态记录链剖分的关键信息：设 $f_{u, i, j}$ 表示考虑 $1 \to u$ 的最长连续链长是 $i$ ， $u$ 当前所在链长是 $j$ ，子树内答案的最大值。

边界条件显然是对于叶子 $u$ ， $f_{u, i, j} = i$ 。

考虑转移， $u$ 选择的 $v$ 继续延续这条链，别的新开一条链。

f_{u, i, j} \leftarrow i + max_{v} {f_{v, max (i, j + 1), j + 1} + \sum_{v^{'} \neq v} f_{v^{'}, i, 1}}

可以把 $\sum_{v^{'} \neq v}$ 拆到 $max$ 的外面去变为 $\sum_{v}$ ，然后 $max$ 内再减去 $f_{v, i, 1}$ 。

答案即为 $f_{1, 1, 1}$ ，时空复杂度 $O (n m^{2})$ 。