P3942 将军令

典型的树形$DP$。

具体思路参考题解

注意：

$dfs2$中，开始一直觉得$pre$没有用，用$fa[x]$不就好了吗？反正你要推到的$u$不是$x$的儿子吗！

结果一直$25分......$

其实呢，在这个搜索中，它的起点不是1可以是任意一个节点

如果还按开始的那个$fa[x]$的话肯定是不行的

$fa[x]$成立仅限于搜索过程是以$1$为节点的深度优先搜索

所以一定要记录$pre$

#include <bits/stdc++.h>
#define ll long long 
#define maxn 200005
using namespace std;
ll n,k,t,hd[maxn],tt=0,u,v,dh[maxn],fa[maxn],vit[maxn],ans;
struct Node{
    ll to,nx;
}e[maxn<<1];
struct node{
    ll fm,dp;
}q[maxn<<1];
inline ll read(){
    ll x=0,f=0;
    char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}
inline void add(ll u,ll v){
    e[++tt].to=v;
    e[tt].nx=hd[u];
    hd[u]=tt;
}
inline void dfs1(ll x){
    for(register int i=hd[x];i;i=e[i].nx){
        ll u=e[i].to;
        if(!dh[u]){
            fa[u]=x;
            dh[u]=dh[x]+1;
            dfs1(u);    
        }
    }
}
inline ll find(ll x){
    ll sp=1;
    while(sp<=k){
        ++sp;
        x=fa[x];
    }
    return x;
}
inline void dfs2(ll x,ll pre,ll sp){
    vit[x]=1;
    if(sp==k)    return;
    for(register int i=hd[x];i;i=e[i].nx){
        ll u=e[i].to;
        if(u!=pre)    dfs2(u,x,sp+1);
    }
}
inline bool cmp(node a,node b){
    return a.dp>b.dp;
}
int main(){
    n=read();k=read();t=read();
    for(register int i=1;i<n;++i){
        u=read();v=read();
        add(u,v);add(v,u);
    }
    dh[1]=1;fa[1]=1;dfs1(1);
    for(register int i=1;i<=n;++i){
        q[i].fm=i;
        q[i].dp=dh[i];
    }
    sort(q+1,q+n+1,cmp);
    for(register int i=1;i<=n;++i){
        node xx=q[i];
        int x=xx.fm;
        if(vit[x])    continue;
        ++ans;
        ll y=find(x);
        dfs2(y,0,0);
    }
    printf("%lld\n",ans);
    return 0;
}