将军令

令 \(f_i\) 表示 \(i\) 子树中最远的未被覆盖的点距离 \(i\) 的距离
令 \(g_i\) 表示 \(i\) 子树中的小队距离 \(i\) 的最近距离。

显然 \(f_u=\max\limits_{v\in son_u} f_v+1,g_u=\max\limits_{v\in son_u} g_v+1\)。

  1. 当 \(g_u>k\) 时，说明这个点不能被覆盖到，令 \(f_u=\max(f_u,0)\)；
  2. 当 \(g_u+f_u<=k\) 时，说明这个点已经被覆盖了，令 \(f_u=-inf\)；
  3. 当 \(f_u=k\) 时，说明这个点需要布置一个小队，\(ans++\)，清空 \(g_u\)，令 \(f_u=-inf\)。

一遍 dfs 维护即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e5+10,inf=1e9;
int n,m,opt,dep[N],ans,f[N],g[N];
vector<int>e[N];
void make_tree(int u,int fa){
    f[u]=0;
    g[u]=inf;
    for(auto v:e[u]){
        if(v==fa){
            continue;
        }
        make_tree(v,u);
        f[u]=max(f[u],f[v]+1);
        g[u]=min(g[u],g[v]+1);
    }
    if(g[u]+f[u]<=m){
        f[u]=-inf;
    }
    if(f[u]==m){
        ans++;
        g[u]=0;
        f[u]=-inf;
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m),read(opt);
    for(int i=1;i<n;i++){
        int u,v;
        read(u),read(v);
        e[u].pb(v);
        e[v].pb(u);
    }
    make_tree(1,1);
    if(f[1]>=0){
        ans++;
    }
    write_endl(ans);
    return 0;
}