P1272 重建道路 分析
__ryp__
·
·
个人记录
设 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)