题意

输入一张图，有 $n-1$ 条边。从 1 开始遍历，问 $d$ 个范围内能访问多少个节点

思路

访问到一个节点，如果当前距离小于等于 $d$，就继续遍历

代码

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100005];
bool f[100005];
int d,cnt;
void dfs(int n,int c){
	if (c <= d){	// 如果当前距离小于 d
		f[n] = 1;	// 标记
		cnt++;
		for (int i = 0;i < a[n].size();i++){
			if (!f[a[n][i]])	dfs(a[n][i],c + 1);
		}
	}

}
int main(int argc, char **argv){
	int n;
	cin >> n >> d;
	for (int i = 1;i < n;i++){
		int u,v;
		cin >> u >> v;
		a[min(u,v)].push_back(max(u,v));	// 从小指向大
	}
	dfs(1,0);
	cout << cnt - 1;	// 去掉 1 节点
	return 0;
}

$2024.1.11$：修改了 DFS 的标记

我的歹马并非如下面两位抄袭歹马

#include<iostream>
#include<vector>
using namespace std;
const int N=114514;
vector<int >g[N];//无向图(邻接表)
bool vis[N];//记录是否走过
int n,d,sum=0;
void dfs(int x,int t)//深度优先
{
 if(t>=d)//再远的就不用搜索了
 {
  return;
 }
 if(!vis[x])//是否走过
 {
  vis[x]=1;//标记
  for(int i=0;i<g[x].size();i++)//遍历每条路(子节点)
  {
   if(!vis[g[x][i]])//是否走过
   {
    sum++;//记录一个居住区
    dfs(g[x][i],t+1);//递归
   }
  }
 }
}
int main()
{
 cin>>n>>d;//输入
 for(int i=0;i<n-1;i++)
 {
  int u,v;
  cin>>u>>v;//输入
  //无向图的边
  g[u].push_back(v);
  g[v].push_back(u);
 }
 dfs(1,0);//深度优先
 cout<<sum;//输出
 return 0;//完结散花
}

洛谷上有一样的题目

#include <bits/stdc++.h>
using namespace std;
vector <int> g[114514];
bool vis[114514];
int ans,n,d;
void dfs(int now,int dis){
	vis[now]=1;
	if(dis==d) return;
	for(int i=0;i<g[now].size();i++){
		if(!vis[g[now][i]]){
			dfs(g[now][i],dis+1);
			ans++;
		}
	}
}
int main(){
	cin>>n>>d;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}

提供一种DFS的解法

#include <bits/stdc++.h>
using namespace std;
vector <int> g[114514];
bool vis[114514];
int ans,n,d;
void dfs(int now,int dis){
	vis[now]=1;
	if(dis==d) return;
	for(int i=0;i<g[now].size();i++){
		if(!vis[g[now][i]]){
			dfs(g[now][i],dis+1);
			ans++;
		}
	}
}
int main(){
	cin>>n>>d;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}