计算机 网站开发 文章小程序企业网站开发

猫猫和企鹅

题目传送门

题目描述

王国里有 $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$ 开始标号。

以下是本人的想法，我一开始利用的是树的重心的算法模板，但是之前用for(int i = h[now]; i != -1; i = ne[i])时输不出结果，最后将当中的“i ！= -1”改成“i”就过了，有大佬能告诉我这两种链表的用法吗？

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = 2 * N;
int n, d, ans;
int e[M], ne[M], h[N], idx;
bool st[N];
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int now, int dis) {st[now] = true;if (dis == d)return;for (int i = h[now]; i; i = ne[i]) {int j = e[i];if (!st[j]) {dfs(j, dis + 1);ans++;}}
}
int main() {scanf("%d%d", &n, &d);for (int i = 1; i <= n - 1; i++) {int u, v;scanf("%d%d", &u, &v);add(u, v);add(v, u);}dfs(1, 0);printf("%d\n", ans);return 0;
}