更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19359545

考虑树上背包。

定义状态 $f_{u, j}$ 表示 $u$ 节点，切掉 $j$ 个所需的最小花费。

那么我们的初始状态就是 $f_{u, 0} = 0$, $f_{u, sz_u} = 1$。

然后我们考虑如何进行转移：

$f_{u, j} = \min(f_{u, j}, f_{u, j - k} + f_{v, k})$

然后考虑我们的答案如何进行计算，显然是 $f_{u, sz_u - p} + f_{u, sz_u}$，这个地方的 $f_{u, sz_u}$ 的值显然是 $1$，但是只有根节点是 $0$。

这个地方实际上就是为了让你的选出来的这 $p$ 个点与你原来的 $u$ 子树脱离，显然需要你删一条父边。

定义 $f(u,k)$ 表示以 $u$ 为根的子树里有 $k$ 个节点与 $u$ 联通的最小道路，$size(u)$ 为 $u$ 的子树内节点个数。

初始状态：$\forall u \in [1,n],f(u,1)=|son_u|$，其中 $|son_u|$ 表示 $u$ 的出边个数。

转移方程：

$$\sum\limits_{v\in son_u,j\in [1,size(u)],k\in [1,size(v)]} f(u,j+k)=\min\{f(u,j)+f(v,k)-2\}$$

其中 $-2$ 是因为最初 $u,v$ 两点的连边被断开，多加的 $2$ 要在这里减回来。

感性理解一下为什么说时间复杂度是 $\Theta(n^2)$ 的：

发现主要的时间复杂度是在 $j,k$ 的枚举上，而 $j,k$ 的枚举其实等价于枚举点对。

原因不难理解，每两个节点只有在它们的 LCA 处会被枚举到。

因此，总的时间复杂度是 $\Theta(n^2)$