自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 23:18:01，当前版本为作者最后更新于2025-06-10 15:45:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

关于 $k-$合法的性质等一些基础内容请参见原版题解。

为了方便，本题解中用 $K$ 表示题目中的限制 $k$。

若我们能重复记起忘记过的事件，那么我们将不只是选出一个形如森林的子图。那我们需要做什么呢？

首先一个事件可以无数次被想起，那么其中有一些是使用回想，一些是使用联想。我们考虑现在在一次记起 $u$ 之后能联想出什么。由于现在的整个联想过程不一定是一棵树，我们把它叫做一个从 $u$ 开始的 $k-$合法过程。我们称 $p_v=u$ 的 $v$ 为 $u$ 的子事件。

那么一个 $k-$合法过程满足以下条件：至多一个子事件处经历一次 $k-$合法过程，其他子事件处可以经历任意多次 $(k-1)-$合法过程。

在这里我们有另一个观察：一个事件处开始的任意多个 $(k-1)-$合法过程都可以与至多一个 $k-$合法过程合并到一起成为一个 $k-$合法过程。

因此接下来我们讨论的将是严格 $k-$合法过程，即不 $(k-1)-$合法的 $k-$合法过程。由以上观察，在一次联想中每个点处开始的所有过程都是对同一个 $j$ 严格 $j-$合法的，否则较小者可以合并到较大者内部。

我们重新表述严格 $k-$合法过程的条件，分两种情况：

1. 一个子事件处开始一次严格 $k-$合法过程，其他子事件处可以对于某个 $j$，开始任意多次严格 $j-$合法过程，其中 $j<k$。
2. 在各个子事件处开始至少两次严格 $(k-1)-$合法过程，其他子事件处可以对于某个 $j$，开始任意多次严格 $j-$合法过程，其中 $j<k-1$。

有了以上结果，我们可以设计状态 dp 了。设 $f_{u,k,i}$ 表示 $u$ 处开始恰好 $i$ 次严格 $k-$合法过程时的最少时间，不包括 $r_u,t_u$。

我们发现这个定义与树形背包比较相似，考虑类似转移。首先计算简单的情况，即 $f_{u,1,1}$。显然 $u$ 处不会开始多于一个 $1-$合法过程。

$$f_{u,1,1}=\sum_{v\in ch(u)}g_{v,0},$$

其中 $g_{v,0}$ 是 $u$ 处不向 $v$ 进行联想所需的最少时间：

$$g_{v,0}=\min_{j\le K,i}\{f_{v,j,i}+ir_v\}.$$

接下来我们要求出对于某个 $v$，它向前置事件转移 $j$ 次严格 $k-$合法过程时的贡献 $g_{v,k,j}$。首先对于 $j\ge1$，我们容易写出：

$$g_{v,k,j}=\min_{i\ge j}\{f_{v,k,i}+jt_v+(i-j)r_v\} $$

可以后缀优化 $O(1)$ 求出。还有一个问题是 $g_{v,k,0}$。我们发现

$$g_{v,k,0}=\min(g_{v,0},\min_{j<k,i}\{f_{v,j,i}+it_v\}). $$

那么我们可以像树形背包一样转移，拆出一维枚举 $u$ 的各个子事件：

$$f_{u,k,i+j,s+1}\leftarrow f_{u,k,i,s}+g_{v,k,j}.$$

最后还有一个 corner case，即上述的情况 2：$f_{u,k,1}$ 可以由 $(k-1)-$合法转移过来，由于当 $i\ge2$ 时 $u$ 处的每个 $(k-1)-$合法过程都对应恰好 一个子事件处的 $(k-1)-$合法过程，我们直接挪用 $f_{u,k-1,i}$ 转移即可。

这个 corner case 中还有一个 corner case：$k=2$ 的时候还可以由一个子事件处恰好一个 $1-$合法过程转移过来。

需要用滚动数组优化一下空间。还有一个空间优化的点在于 $f_{u,k,i}$ 中的 $i$ 一维不会超过 $\dfrac n2$。