题解：P15902 [TOPC 2025] Gas Station

· · 题解

题意

一个树上，可以放置 k 个休息站，求存在放置休息站方案数的最小 d 。

解决

发现 d 越大，条件越松，故二分 d 。 现在只需要找到在 d 确定时的最少休息站个数，如果 \le k 说明成立。

考虑树上dp。

我们定义 f_u 表示以 u 为根的子树，合法最小休息站个数， 定义 g_u 表示以 u 为根的子树中，到 u 节点最远的休息站。

设 v 是 u 的子节点，边权为 w，那么就有两种情况：

若 g_u+w \ge mid 则 v 上要建休息站，f_v=f_v+1，g_v=0 ；

记最大的 g_u+w 为 mx，次大的为 snd，若 mx+snd \ge mid 那么 u 需要建立休息站，f_u=f_u+1，g_u=0 。

最后 f_u=f_u+f_v 。

相应维护 g_u，mx，snd 即可，这很简单

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
const int INF = 0x3f3f3f3f;
int n, k;
struct edge {
    int v, w;
};
vector<edge>e[N];
int l = 0, r = 0;
int f[N], g[N];
void dfs(int u, int fa, int x) {
    int mx = -1e18, snd = -1e18;
    for (auto [v, w] : e[u]) {
        if (v == fa) continue;
        dfs(v, u, x);
        if (g[v] + w > x) g[v] = 0, f[v] += 1;//v上放个
        snd = max(snd, min(mx, g[v] + w));
        mx = max(mx, g[v] + w);
        g[u] = max(g[u], g[v] + w);
    }
    if (snd + mx > x) f[u] += 1, g[u] = 0; //u上放个
    for (auto [v, w] : e[u]) {
        if (v == fa) continue;
        f[u] += f[v];
    }
}
bool check(int x) {
    for (int i = 0; i <= n; i++) f[i] = g[i] = 0;
    dfs(1, 0, x);
    return f[1] <= k;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> k;
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
        l = max(l, w);
        r += w;
    }
    int ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}

时间复杂度 O(n \cdot log_2n)