题解 洛谷 P1272 树形dp

· · 个人记录

前言

用时：物理课想出思路，音乐课一遍过。

题意

给出 n 个点的树，求从中分裂出一棵大小为 p 的树，最少要删几条边。

思路

不妨设 f_{u,i} 表示以 u 为根的子树中，删去至少 f_{u,i} 条边就可获得 p 子树。

暂且不谈状态转移，当前的问题是删去的边可以不在 u 子树中，难道需要换根法解决吗？

仔细想想，其实不用。我们只需删去 u->father 这条边，就能将 u 子树分离出来了。

进一步的，我们发现 u->v 这条边删或不删，仅仅会对 v 子树中，以 v 为根的那棵分离子树产生影响。

换句话说，f_{u,i} 中的 i 只需表示以 u 为根的分离子树大小即可，因为只有它会影响 f_{u->father} 这个状态。而 u 的其它分离子树的答案已经被计算过了，这一点可以由递归序保证。

那么不难想出状态转移：

考虑逐步将 u 的子树添加，那么对于 u->v 这条边，有删或不删两种选择。

定义 f2 是 f 的滚动数组。则对于“删”这个决策有：f_{u,i}=f2_{u,i}+1。

对于“不删”有：f_{u,i+j}=f2_{u,i}+f_{v,j}。

计算答案：ans=\min f_{u,p}+1。

其实本质上还是背包。

提交记录。