题解：P15902 [TOPC 2025] Gas Station

ZMQ_Ink6556 · 2026-03-27 21:12:59 · 题解

题解：P15902 [TOPC 2025] Gas Station

解题思路

发现已知 d 去求 k 是容易的，所以考虑二分 d，每次判断对应的 k 和给定的 k 的大小关系。

关于 check() 怎么写：

首先从树中截取出一条链的路径，然后取其中两个加油站之前的部分观察：

则这段中最长的路径长度就是两个红点之间的距离。

因此问题转化为让两个加油站之前的距离 \le d。

我们钦定 1 号点为根节点，则问题转化为树上 dp。

首先很明显的一个结论：若红点放在节点 p 和节点 fa_p 都能满足目前最长链 \le d 那么放在 fa_p 是一定不劣的。这是因为放在 fa_p 说明 fa_p 的子树内部已经全部合规且向上的贡献会比 p 小 mp_{p , fa_p}。

所以我们可以在处理到每个点的时候，判断以下两种情况：

• 若 dp_p \le d 但 dp_{fa_p} > d，则在 p 放加油站，k \leftarrow k + 1。
• 若存在一组点 p , q 满足 fa_p = fa_q 且 dp_p + mp_{p , fa_p} + dp_q + mp_{q , fa_q}，则在 fa_p 放加油站，k \leftarrow k + 1。

这两个操作都可以在 fa_p 位置合并，记录最子节点大值和次大子节点值即可。

dp 数组初始化和转移也很明显：

所有叶子和放加油站的地方 dp_i 为 0，否则为 \max\limits_{i \in som_p} (dp_p + mp_{p , i})。

至于为什么钦定 1 为根是正确的，因为换个根只是把一些节点的两种转移情况反过来了，对答案是没有影响的。

参考代码

注意别忘了清空 dp 数组。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct p
{
    int v , w;
};
int n , k , u , v , w , l , r = 10000000000000016ll , mxk , mid , ans , dp[200005] , cnt;
vector<p> mp[200005];
inline void dfs(int p , int f)
{
    int mx = 0;
    for(int i = 0 ; i < mp[p].size() ; i++)
    {
        if(mp[p][i].v == f)
        {
            continue;
        }
        dfs(mp[p][i].v , p);
        if(dp[mp[p][i].v] + mp[p][i].w > mid)
        {
            dp[mp[p][i].v] = 0;
            cnt++;
        }
        if(!dp[p])
        {
            dp[p] = dp[mp[p][i].v] + mp[p][i].w;
        }
        else if(!mx)
        {
            mx = dp[mp[p][i].v] + mp[p][i].w;
        }
        else
        {
            mx = max(mx , dp[mp[p][i].v] + mp[p][i].w);
        }
        if(mx > dp[p])
        {
            swap(mx , dp[p]);
        }
    }
    if(dp[p] + mx > mid)
    {
        cnt++;
        dp[p] = 0;
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 1 ; i < n ; i++)
    {
        cin >> u >> v >> w;
        mp[u].push_back({v , w});
        mp[v].push_back({u , w});
        mxk = max(mxk , w);
    }
    l = ans = mxk;
    while(l <= r)
    {
        mid = (l + r) / 2;
        for(int i = 0 ; i <= n ; i++)
        {
            dp[i] = 0;
        }
        cnt = 0;
        dfs(1 , 0);
        if(cnt <= k)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}