LuoGu - P3698 - [CQOI2017]小Q的棋盘#
题意#
给定一棵 个节点的有根树，定义一次移动为：从当前所在节点移动到一个相邻节点。问从根节点出发，移动 次后，最多经过多少个不同的节点。
每个节点可以被重复经过，但只计算一次。
.
分析#
这道题可以用树形 DP 来做，这里只提供时间复杂度更优的贪心做法。
首先很容易想到，我们要尽可能保证每一次移动都到达一个新的节点，所以要先向深度最深的节点走。
如果走的过程中， 次移动机会就用完了，答案即为 .
若否，我们要耗费尽可能少的移动次数，来到达一个新的节点。可以发现，在走完最长链之后，每到一个新节点都只需要 步。
如上图所示。先选择最长链 . 此时如果要再添加点，只需要找一个与任意一个被选节点相邻的节点即可。
比如选择了点 ，那路径就变成：.
由于每次新选的点，都与一个路径中的点相邻，所以只要在路径中插入两步，一定可以走到这个新的节点。
因此，在选完最长链之后，剩余的步数每两步都可以走到一个新的节点。
形式化地，设这棵树的节点个数为 ，最长链长度为 ，可用步数为 ，可以这样表示出答案：
- 若 ，步数只够在最长链上移动，则答案为 .
- 若 ，走完最长链之后有剩余步数，则答案为：
这里注意，如果步数足够多，也最多只能走完所有点，此时答案为 .
时间复杂度为 .
代码#
#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;
}