题目内容

米小游有一个 $n$ 个节点的树，树根编号为 $1$ 。

米小游可以在叶子节点上添加一个新的儿子节点，添加后，添加的节点变成了新的叶子节点。

思路：DFS

以 $1$ 号点为根，求出从 $1$ 号点到所有点的距离，如果距离小于等于 $k$ ，则将这个点加入到答案中。

此外，对于一个叶子节点，如果其距离 $d$ 小于 $k$ ，则说明还可以在这个叶子下添加 $k - d$ 个点，这些点成一条链。

所以，在进行以 $1$ 号点为根的树的遍历的过程中，即可获得从 $1$ 号点到每个点的距离，同时进行判断和答案计算即可。

时间复杂度：$O(n)$