题解：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 的原贡献加上新贡献

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])));
        }
    }

最后注意一下多测清空