标签：企鹅 idx int P5908 dfs 猫猫居住区

P5908 猫猫和企鹅

题目描述

王国里有 n 个居住区，它们之间有 n−1条道路相连，并且保证从每个居住区出发都可以到达任何一个居住区，并且每条道路的长度都为 1。

除 1 号居住区外，每个居住区住着一个小企鹅，有一天一只猫猫从 1号居住区出发，想要去拜访一些小企鹅。可是猫猫非常的懒，它只愿意去距离它在 d以内的小企鹅们。

猫猫非常的懒，因此希望你告诉他，他可以拜访多少只小企鹅。

输入格式

第一行两个整数 n,d意义如题所述。

第二行开始，共 n−1 行，每行两个整数 u,v，表示居民区 u和 v 之间存在道路。

输出格式

一行一个整数，表示猫猫可以拜访多少只小企鹅。

输入输出样例

输入 #1

输出 #1

说明/提示

对于 100% 的数据，满足 1≤n,d≤10⁵，保证所有居民区从 1开始标号。

分析：

树用无向图存-->邻接表

然后dfs从猫的位置即1号位开始搜

#include<bits/stdc++.h> using namespace std; const int N=100010; const int M=200006; int n,d; int h[N]; int e[M]; int ne[M]; int idx; bool st[N]; int cnt=0;//可拜访 void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx; idx++; } void dfs(int t,int b){//点，距离 if(b==d){ //现在距离到d退出递归 return; } for(int i=h[t];i!=-1;i=ne[i]) { int f=e[i]; if(!st[f]){ st[f]=true; cnt++;//小于等于d都会加1 dfs(f,b+1);//遍历下一层点 } } } int main(){ cin>>n>>d;//n个点，d距离 int a,b; memset(h,-1,sizeof h) ; for(int i=1;i<n;i++){ cin>>a>>b; add(a,b); add(b,a); } st[1]=true;//第一个点是猫的位置不能返回 dfs(1,0); cout<<cnt; return 0; }

标签：企鹅,idx,int,P5908,dfs,猫猫,居住区
From： https://www.cnblogs.com/luckyhappyyaoyao/p/18341581

P5908