定义 $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)$