题意

给定一棵 $n$ 个节点的有根树，定义一次移动为：从当前所在节点移动到一个相邻节点。问从根节点出发，移动 $k$ 次后，最多经过多少个不同的节点。

每个节点可以被重复经过，但只计算一次。

$n\leq 100$.

分析

这道题可以用树形 DP 来做，这里只提供时间复杂度更优的贪心做法。

首先很容易想到，我们要尽可能保证每一次移动都到达一个新的节点，所以要先向深度最深的节点走。

如果走的过程中，$k$ 次移动机会就用完了，答案即为 $k$.

若否，我们要耗费尽可能少的移动次数，来到达一个新的节点。可以发现，在走完最长链之后，每到一个新节点都只需要 $2$ 步。

如上图所示。先选择最长链 $1\to 2\to 5\to 9\to 12$. 此时如果要再添加点，只需要找一个与任意一个被选节点相邻的节点即可。

比如选择了点 $4$，那路径就变成：$1\to 2\to 4\to 2\to 5\to 9\to 12$.

由于每次新选的点，都与一个路径中的点相邻，所以只要在路径中插入两步，一定可以走到这个新的节点。

因此，在选完最长链之后，剩余的步数每两步都可以走到一个新的节点。

形式化地，设这棵树的节点个数为 $n$，最长链长度为 $l$，可用步数为 $k$，可以这样表示出答案：

• 若 $k\leq l – 1$，步数只够在最长链上移动，则答案为 $k$.
• 若 $k > l – 1$，走完最长链之后有剩余步数，则答案为：

这里注意，如果步数足够多，也最多只能走完所有点，此时答案为 $n$.

时间复杂度为 $\mathcal{O}(n)$.

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 108;
int n, k;
struct Edge{
    int to, nxt;
}edge[MAXN << 1];
int head[MAXN], e_cnt = 0;
void add(int u, int v) {
    edge[++e_cnt].to = v;
    edge[e_cnt].nxt = head[u];
    head[u] = e_cnt;
}
int deepest = 1;//最长链的长度
void dfs(int x, int fa, int dep) {
    deepest = max(deepest, dep);
    for(int i = head[x]; i; i = edge[i].nxt) {
        int v = edge[i].to; if(v == fa) continue;
        dfs(v, x, dep + 1);
    }
}
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++) {
        int a, b; scanf("%d%d", &a, &b); a++, b++;
        add(a, b); add(b, a);
    }
    dfs(1, 0, 1);
    if(deepest >= k + 1) cout << k + 1 << endl;
    else cout << min(deepest + (k - deepest + 1) / 2, n);
    return 0;
}