题解：P12777 理解加强版

VinstaG173 · 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-合法过程的条件，分两种情况：

有了以上结果，我们可以设计状态 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。

事实上严格 k-合法的树大小为 \Omega(2^k)，因此 f_{u,k,i} 中的 i 一维不会超过 \dfrac{n}{2^k}，因此总时间复杂度为 O(n^2)。实现优秀的话常数很小，可以通过。

题解：P12777 理解 加强版