P1272 重建道路

不妨在计算每个节点 $u$ 的答案时, 强制选择 $u$, 之后统计每个节点答案的最小值.
设对于节点 $u$, 目前选择前 $k$ 个子节点, 子树大小为 $s$ 的最小删边数为 $f[u][k][s]$ .
考虑转移. 其实就是找到每个子节点 $v$ 的一种分配方案, 子树大小为 $s_v$ , 删边数为 $h_v$ , 使得 $\sum s_v = s - 1$ , 且 $\sum h_v$ 最小.
这就相当于一个背包问题. 写出转移方程:
$$ f[u][k][s] = \min (f[u][k - 1][s], f[u][k - 1][s - s_v] + f[v][s_v]) $$
可以用滚动数组滚掉 $k$ 这一维.
初始 $f[u][1] = 0$ (只选择这个节点), 其余为正无穷.
注意统计答案时, 对于每个非根节点, 由于其与父节点的连边需要断开, 答案要 $+1$ .