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

· · 题解

一道贪心题，本人感觉这题有绿的难度。

题意

一棵树，要求在上面标记点，使得任意一条长度为 k 的简单路径都至少含有一个被标记的点。求最少标记多少点。

转化一下题意，给每一个叶子节点都向外扩展出一个虚拟的被标记的点，合法方案即任意两个被标记的点，若它们之间没有其他被标记的点，则它们的简单距离不超过 k+1。

思路

定义 d_i 表示 i 节点子树中，i 与一个被标记的、到 i 简单路径中没有其他点被标记（包括本身）的点的简单路径长度的最大值。

如果一个点 u，如果它有一个子节点的 d 大于等于 k，或是对于它的任意两个不同的子节点 v_1、v_2，有 d_{v_1}+d_{v_2}\ge k，那么就需要标记这个点，否则不用。

贪心正确性

如果有一个点，它没有满足上述思路的标记条件，但被标记了，那么它可能会使用同样的标记数，它的祖先节点的 d 没有上述思路生成的小。这一定不是最优的。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
long long n,m,d[maxn],ans;
vector<int> a[maxn];
void dfs(int u,int fa)
{
    int max1=0,max2=0;//最大和次大的d
    for(int v:a[u])
    if(v!=fa)
    {
        dfs(v,u);
        if(d[v]>max1)
        {
            max2=max1;
            max1=d[v];
        }
        else if(d[v]>max2)
        max2=d[v];
    }
    if(max1+max2>=m)
    {
        ans++;
        d[u]=0;
    }
    else
    d[u]=max1+1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1,0);
    cout<<ans;
}