题解：P12659 [KOI 2023 Round 1] 加油站

Reply_ · 2025-06-01 13:59:46 · 题解

题目传送门

思路

树上问题，贪心解决。

题面告诉我们每一条长度大于等于 k 的路径上都必须要有一座加油站。

对于树上的关于路径的问题，我们对于路径两端点的 \operatorname{LCA} 考虑。

处于贪心的思想，对于一个点而言，我们会在不得不建加油站的时候建立加油站，怎么判断一个点是不得不建加油站呢，就是这个点的子树内有一条没有建立过加油站的路径，其长度大于等于 k 的时候，我们不得不建加油站。

为什么这个贪心是对的，也很显然，我们希望一个加油站能影响更多的路径，所以应越靠近根节点越好，所以应当这么做。

实现

定义 sum_i 代表以 i 为根的子树中离 i 最远的点距离 i 的距离，但是这个点到 i 的路径上不能有加油站建立过。

这样对于枚举到的 u，如果有两棵子树的 sum 的和加 2 大于等于 k 那么就要建加油站（或者某一棵子树连到 u 的时候直接就超过 k 了，也要建）。

注意：如果决定要建加油站，那么把 sum 赋值为 -1，这样向上传递的时候才不会出错（其父节点的 sum 为零）。

代码

#include<bits/stdc++.h>
#define ll long long
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=2e5+10;
int n,k;
vector<int>g[N];
void add(int ui,int vi)
{
    g[ui].push_back(vi);
    return;
}
int sum[N];//以i为根的子树中离i最远的未被覆盖的点距离i的距离
void dfs(int u,int fa)
{
    sum[u]=0;
    for(int i = 0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fa) continue;
        dfs(v,u);
        sum[u]=max(sum[u],sum[v]+1);
    }
    int maxn=-1e9;
    for(int i = 0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fa) continue;
        if(sum[v]+1>=k){
            vis[u]=1;
            sum[u]=-1;
            break;
        }
        if(maxn+2+sum[v]>=k){
            vis[u]=1;
            sum[u]=-1;
            break;
        }
        maxn=max(sum[v],maxn);  
    }
    return;
}
signed main()
{
    n=read(),k=read();
    F(i,1,n-1){
        int ui=read(),vi=read();
        add(ui,vi);
        add(vi,ui);
    }
    dfs(1,0);
    int sum=0;
    for(int i = 1;i<=n;i++){
        sum+=vis[i];
    }
    cout << sum << '\n';
    return 0;
}
/*

*/