LuoguP3942 将军令

题面

给一颗树，每次选一个点，覆盖该点及其周围与其距离不超过k的节点，求最少需要选多少个点。

题解

贪心，每次取深度低的没取的点的K级祖先

显然这样最优

#include<bits/stdc++.h>

using namespace std;

#define LL long long

inline LL read()
{
    LL f = 1,x = 0;
    char ch;
    do
    {
        ch = getchar();
        if(ch == '-') f=-1;
    }while(ch<'0'||ch>'9');
    do
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }while(ch>='0'&&ch<='9');
    return f*x;
}

const int MAXN = 1e5 + 10;

int n,k,t;
int fa[MAXN];
int head,tail,q[MAXN];
vector<int>ve[MAXN];
int dp[MAXN];

inline void BFS()
{
    head = 1,tail = 1;
    q[head]=1;
    while(head<=tail)
    {
        int x = q[head];head++;
        for(int i=0;i<ve[x].size();i++)
        {
            int v = ve[x][i];
            if(!fa[v])
            {
                fa[v] = x;
                q[++tail]=v;
            }
        }
    }
}

inline void color(int now)
{
    if(!dp[now]) return;
    for(int i=0;i<ve[now].size();i++)
    {
        int v = ve[now][i];
        if(dp[v]<dp[now]-1)
        {
            dp[v]=dp[now]-1;
            color(v);
        }
    }
}

int main()
{
    n = read(),k = read(),t = read();
    for(int i=1;i<n;i++)
    {
        int u = read(),v = read();
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    fa[1]=1;
    BFS();
    int ans = 0;
    memset(dp,-1,sizeof(dp));
    reverse(q+1,q+n+1);
    for(int i=1;i<=n;i++)
    {
        if(dp[q[i]]==-1)
        {
            ans++;
            int now = q[i];
            for(int j=1;j<=k;j++) now = fa[now];
            dp[now]=k;
            color(now);
        }
    }
    cout<<ans<<endl;
}