这个问题可以用贪心解决。

可以发现，每个节点的所有叶子节点中，真正起约束作用的是深度最大的那个。

因为大的满足了，小的一定也满足。

这样dfs函数返回一个当前点最深的叶子的距离即可。

每次处理完所有子节点之后排个序就行了。

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 int n,k; 7 int hd[1000005],to[2000005],nx[2000005],ec; 8 int deg[1000005]; 9 10 int read()11 {12     int ret=0;char c=getchar();13     while(c<'0'||c>'9')c=getchar();14     while(c>='0'&&c<='9')ret=ret*10+c-'0',c=getchar();15     return ret;16 }17 18 void edge(int af,int at)19 {20     to[++ec]=at;21     nx[ec]=hd[af];22     hd[af]=ec;23     deg[at]++;24 }25 26 int st[1000005],tp;27 int ans;28 29 int dfs(int p,int fa)30 {31     if(deg[p]==1)return 0;32     int l=tp+1;33     tp+=deg[p]-1;34     int r=l;35     for(int i=hd[p];i;i=nx[i])36         if(to[i]!=fa)37             st[r++]=dfs(to[i],p)+1;38     r--;39     sort(st+l,st+r+1);40     while(r-l&&st[r]+st[r-1]>k)r--,ans++;41     return st[r];42 }43 44 int main()45 {46     scanf("%d%d",&n,&k);47     for(int i=1;i