P5908 猫猫和企鹅
题目描述
王国里有 \(n\) 个居住区，它们之间有 \(n-1\) 条道路相连，并且保证从每个居住区出发都可以到达任何一个居住区，并且每条道路的长度都为 \(1\)。
除 \(1\) 号居住区外，每个居住区住着一个小企鹅，有一天一只猫猫从 \(1\) 号居住区出发，想要去拜访一些小企鹅。可是猫猫非常的懒，它只愿意去距离它不大于 \(d\) 的小企鹅们。
猫猫非常的懒，因此希望你告诉他，他可以拜访多少只小企鹅。
输入格式
第一行两个整数 \(n, d\)，意义如题所述。
第二行开始，共 \(n - 1\) 行，每行两个整数 \(u, v\)，表示居民区 \(u\) 和 \(v\) 之间存在道路。
输出格式
一行一个整数，表示猫猫可以拜访多少只小企鹅。
输入输出样例 #1
输入 #1
5 1
1 2
1 3
2 4
3 5
输出 #1
2
说明/提示
对于 \(100\%\) 的数据，满足 \(1 \le n ,d \le 10^5\)，保证所有居民区从 \(1\) 开始标号。
题目解析
典型的树形结构遍历，我主要讲一下dfs()函数的写法
首先数据方面，我推荐使用STL的vector数组这个数据结构来储存树
vector<int> g[N];
int n,d,ans;
dfs()函数需要三个参数:
1.p,表示现在的节点
2.deep,表示现在的深度
3.fa,表示该节点的父亲节点
当deep>d时,说明小猫不能再往下走了,直接return
当deep<=d时,说明能拜访这个节点ans++
该节点p的邻接点分别遍历(节点为i，深度deep+1，父亲节点为p)
注：父亲节点(fa)不可重复遍历！！！
所以一旦i=fa，就要continue
dfs()如下
void dfs(int p,int deep,int fa){if(deep>d) return;ans++;for(auto v:g[p]){if(v==fa) continue;dfs(v,deep+1,p);}
}
写出了dfs那么剩下的就好写了
ACcode:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> g[N];
int n,d,ans;
void dfs(int p,int deep,int fa){if(deep>d) return ;ans++;for(auto v:g[p]){if(v==fa) continue;dfs(v,deep+1,p);}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>d;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0,1);cout<<ans-1<<endl;return 0;
}
//AAA_jiancaipifa
OS:这小猫太懒了