题解：P12734 理解

本题我们可以先定义一个直接出答案的状态：

f_{u,i}

表示以

u

为根的子树内记忆容量为

i

的最少时间，特别地，

f_{u,0}

表是以

u

为根的子树内，不选

u

的最少时间。

则答案应为

f_{0,0}

，所以

f_u

应该不记录

u

的贡献。

对于状态转移，首先有：

f_{u,1} = \sum_{v \in son(u)} \min(f_{v,0},f_{v,k}+r_v)

\infty & u \in x \\ f_{u,1} & u \notin x \\ \end{cases}$$ 考虑 $i \in [2,k]$，有三种转移情形： 1. $v$ 不选，此时用于转移的是 $f_{v,0}$ 2. $v$ 作为根，此时用于转移的是 $f_{v,k}+r_v$ 3. $v$ 作为 $u$ 的儿子，此时用于转移的是 $f_{v,i-1}+t_u$ 但是，我们发现，对于 $u$ 子树和 $i$ 的记忆容量，$u$ 的儿子中可以有**最多一个**记忆容量为 $k$，其余都为 $k-1$。 这时，我们可以按以下方式处理，就是先算出和再减去 $v$ 的原贡献加上新贡献 ```cpp F(i,2,k){ ll s = 0; for (auto v:go[u]){ s += min(dp[v][0],min(dp[v][k]+ar[v],dp[v][i-1]+br[v])); } dp[u][i] = s; for (auto v:go[u]){ dp[u][i] = min(dp[u][i],s-min(dp[v][0],min(dp[v][k]+ar[v],dp[v][i-1]+br[v]))+min(dp[v][0],min(dp[v][k]+ar[v],dp[v][i]+br[v]))); } } ``` 最后注意一下多测清空

文章操作