题解：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

没有上述思路生成的小。这一定不是最优的。

代码

CPP

#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;
}

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

文章操作

题意

思路

贪心正确性

代码

相关推荐

评论

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