P5908 猫猫和企鹅

题目描述

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

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

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

输入格式

第一行两个整数 ，意义如题所述。

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

输出格式

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

输入输出样例 #1

输入 #1

5 1
1 2
1 3
2 4
3 5

输出 #1

2

说明/提示

对于 的数据，满足 ，保证所有居民区从 开始标号。

题解

观察题目

解这道题很明显要找出离1号社区的距离不大于d的所有社区，是一个图的遍历问题。又因为n个社区只有n-1条道路，又退化成了树的遍历问题。

那我们可以用DFS算法，每往下遍历一层距离dist+1，同时sum+1。当dist≥d时，结束此次遍历。最终的sum值就是符合条件的社区数，即猫猫可以拜访的企鹅数。

代码

#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;

const int max_size=1e5+5;
int n,d;
int sum=0;
vector<int> e[max_size];

int readint(){	//快速读入 
	char ch=getchar();
	int x=0;
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x;
}

void dfs(int u,int fa,int di){
    if(di>=d) return;
    for(int i=0;i<e[u].size();i++){
        if(e[u][i]!=fa){
            dfs(e[u][i],u,di+1);
            sum++;
        } 
    }
}

void f(){
    n=readint();d=readint();
    int u,v;
    for(int i=1;i<n;i++){
        u=readint();v=readint();
        e[u].push_back(v);e[v].push_back(u);
    }
    dfs(1,0,0);
    printf("%d",sum);
}

int main(){
    f();
    return 0;
}