【题目来源】https://www.luogu.com.cn/problem/P5908【题目描述】王国里有 n 个居住区它们之间有 n−1 条道路相连并且保证从每个居住区出发都可以到达任何一个居住区并且每条道路的长度都为 1。除 1 号居住区外每个居住区住着一个小企鹅有一天一只猫猫从 1 号居住区出发想要去拜访一些小企鹅。可是猫猫非常的懒它只愿意去距离它不大于 d的小企鹅们。猫猫非常的懒因此希望你告诉他他可以拜访多少只小企鹅。【输入格式】第一行两个整数 n,d意义如题所述。第二行开始共 n−1 行每行两个整数 u,v表示居民区 u 和 v 之间存在道路。【输出格式】一行一个整数表示猫猫可以拜访多少只小企鹅。【输入样例】5 11 21 32 43 5【输出样例】2【数据范围】对于 100% 的数据满足 1≤n,d≤10^5保证所有居民区从 1 开始标号。【算法分析】● 题目给了 n 个节点、n-1 条边这是一棵树以及一个阈值 d要求统计深度 ≤ d 的节点数排除根节点。这其实就是求树中所有节点的深度然后统计深度不超过 d 的节点个数。● 注意输出结果的那个循环的循环变量从i2启动表示直接跳过根节点执行遍历写法简洁且执行效率更高。因为本题代码中根结点 1 的 dep[1]0也满足小于阈值 d 的约束但其不能计入总数。【算法代码】#include bits/stdc.h using namespace std; const int N1e55; vectorint g[N]; int st[N],dep[N]; int n,d; void dfs(int u,int fa) { st[u]true; dep[u]dep[fa]1; for(int i0; ig[u].size(); i) { int tg[u][i]; if(!st[t]) dfs(t,u); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cinnd; for(int i1; in; i) { int x,y; cinxy; g[x].push_back(y); g[y].push_back(x); } dep[0]-1; dfs(1,0); int cnt0; for(int i2; in; i) { if(dep[i]d) cnt; } coutcnt; return 0; } /* in: 5 1 1 2 1 3 2 4 3 5 out: 2 */【参考文献】https://www.luogu.com.cn/problem/solution/P5908