题解：P14740 [ICPC 2021 Seoul R] Logistical Warehouse 2

kaikai_qwq · 2026-11-13 18:02:34 · 题解

考虑贪心加 DP。

考虑抽象为一个覆盖问题，每次选择一个点，就会覆盖所有离其距离 \le k 的点。

我们维护 dp_{u, 0} 表示 u 子树内，距离最近的选择的点；dp_{u, 1} 表示 u 子树内，距离 u 最远的未覆盖的点，若都覆盖为 -1。

转移是容易的：

若 dp_{u, 1}\ge k，显然必须选择 u 覆盖，此时答案增加 1，令 dp_{u, 1} = -1, dp_{u, 0} = 0。

若 dp_{u, 0} + dp_{u, 1}\le k，则 dp_{u, 0} 对应这个选择的点可以覆盖到所有未覆盖的点，令 dp_{u, 1} = -1。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
int n, k;
int dp[MAXN][2];
int ans;
vector <int> G[MAXN];
void dfs(int u, int fa) {
    dp[u][0] = 1e18;
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        dp[u][0] = min(dp[u][0], dp[v][0] + 1);
        dp[u][1] = max(dp[u][1], dp[v][1] + 1);
    }
    if (dp[u][1] >= k) {
        ans++;
        dp[u][1] = -1;
        dp[u][0] = 0;
    }
    if (dp[u][0] + dp[u][1] <= k) dp[u][1] = -1;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    if (dp[1][1] != -1) ans++; // 注意这里，未覆盖完还需要再选一个
    cout << ans;
    return 0;
}