题目描述
一个节点数为 $n$ 的树，从节点 $0$ 出发走 $m$ 步做多可以走多少个节点（可以经过一个节点多次）。
输入格式
第一行包含2个正整数 $V, N$，其中 $V$ 表示格点总数，$N$ 表示移动步数。
接下来 $V-1$ 行，每行两个数 $a_i,b_i$，表示编号为$a_i,b_i$ 的两个格点之间有连线。
输出格式
输出一行一个整数，表示最多经过的格点数量。
样例 #1
样例输入 #1
5 2
1 0
2 1
3 2
4 3
样例输出 #1
3
样例 #2
样例输入 #2
9 5
0 1
0 2
2 6
4 2
8 1
1 3
3 7
3 5
样例输出 #2
5
提示
【输入输出样例 1 说明】
从格点 $0$ 出发移动 $2$ 步。经过 $0, 1, 2$ 这 $3$ 个格点。
【输入输出样例 2 说明】
一种可行的移动路径为 $0 \to 1 \to 3 \to 5 \to 3 \to 7$，经过 $0, 1, 3, 5, 7$ 这 $5$ 个格点。
【数据规模与约定】
对于 $100\%$ 的测试点，$1\le N,V ≤ 100$，$0 ≤a_i,b_i< V$。
题解 1
以一条链为例，每走一步会多经过一个新的点；
当该链全部被遍历时，可以尝试走子节点，此时平均需要花费 $2$ 步来经过一个新的点（去+回）；
因此显然是一个贪心问题，只需讨论最长链的长度与 $m$ 的关系即可。
代码 1
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
vector<int> G[N];
int d[N];
int maxd = 1;
void dfs(int u, int fa) {
for (int v : G[u]) {
if (v != fa) {
d[v] = d[u] + 1;
maxd = max(maxd, d[v]);
dfs(v, u);
}
}
}
int main() {
cin >> n >> m;
for (int i = 1;i < n;i++) {
int u, v; cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
d[0] = 1;
dfs(0, 0);
if (maxd >= m) cout << min(m + 1, maxd) << '\n';
else cout << min(n, maxd + ((m - maxd + 1) >> 1)) << '\n';
return 0;
}