代码

#include<bits/stdc++.h>
using namespace std;
struct point{
	int depth,num;
	bool cover;
	friend bool operator < (point r,point c){
		return r.depth<c.depth;
	}
}node[100005];
int n,k,ans=0;
vector<int> e[100005];
struct bfspoint{
	int pointnum,father;
	int level;
};
queue<bfspoint> q;
priority_queue<point> pq;
bool flag=0;
void findkfa(int start,int finddis){
	if(finddis==0||start==1){//找到了第k级父节点或已经在根节点了，没有更浅的点了 
		node[start].cover=1;
		bfspoint temp2;
		temp2.pointnum=start;
		temp2.father=start;
		temp2.level=0;
		q.push(temp2);
		while(!q.empty()){
			temp2=q.front();
			q.pop();
			for(unsigned int i=0;i<e[temp2.pointnum].size();i++){
				if(e[temp2.pointnum][i]!=temp2.father){
					if(temp2.level+1<=k){
						node[e[temp2.pointnum][i]].cover=1;
						bfspoint nw;
						nw.father=temp2.pointnum;
						nw.level=temp2.level+1;
						nw.pointnum=e[temp2.pointnum][i];
						q.push(nw);
					}
				}
			}
		}
		flag=1;
		return ;
	}
	for(unsigned int i=0;i<e[start].size();i++){
		if(node[e[start][i]].depth<node[start].depth){
			findkfa(e[start][i],finddis-1);//找k个更浅的节点 
			if(flag==1){
				return ;
			}
		}
	}//没有找到深度更前的节点了（目前已经在根节点了）
}
int main(){
//	freopen("rebody.in","r",stdin);
//	freopen("rebody.out","w",stdout);
  	int ttt;
	scanf("%d%d%d",&n,&k,&ttt);
	int ca,cb;
	for(int i=1;i<=n-1;i++){
		scanf("%d%d",&ca,&cb);
		node[ca].num=ca;
		node[cb].num=cb;
		e[ca].push_back(cb);
		e[cb].push_back(ca);//存边
	}
	if(k==0){
		cout<<n;
		return 0;
	}//小小的特判
	node[1].depth=1;
	bfspoint temp1;
	temp1.pointnum=1;
	temp1.father=1;
	q.push(temp1);//以任意一点作为根节点
	while(!q.empty()){
		temp1=q.front();
		q.pop();
		for(unsigned int i=0;i<e[temp1.pointnum].size();i++){
			if(e[temp1.pointnum][i]!=temp1.father){
				node[e[temp1.pointnum][i]].depth=node[temp1.pointnum].depth+1;
				bfspoint nw;
				nw.pointnum=e[temp1.pointnum][i];
				nw.father=temp1.pointnum;
				q.push(nw);
			}
		}
	}
	// for(int i=1;i<=n;i++){
	// 	cout<<node[i].depth<<" ";
	// }//测试输出每个点的深度
	for(int i=1;i<=n;i++){
		pq.push(node[i]);
	}
	point temp3;
	while(!pq.empty()){
		temp3=pq.top();
		pq.pop();
		if(node[temp3.num].cover==0){
			flag=0;
			findkfa(temp3.num,k);
			ans++;
		}
	}
	cout<<ans;
	return 0;
}