本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-18 11:04:43

设 $f(u, k)$ 代表在 $u$ 的子树上，需要删掉多少条边才能得到一个大小为 $k$ 的子树。初始地，$f(u, 1) = 0$，$f(u,k) = \infty \space \text{s.t.} \space k \neq 1$。

那么对于每一个孩子，我们如果不用它，那么就是 $f(u, k) + 1$，因为需要删掉这条边。

否则，如果用这个孩子 $v$ 来更新 $u$，我们就有：

$f(u, k) = f(u, j) + f(v, k - j), \space 0 \le j \le k - 1$

所以总的方程：

$$ f(u, k) = \min\limits_{v} f(u, k) + 1, f(u, j) + f(v, k - j) $$