php网站开发框架,网站关键词搜索排名优化,百度热搜排名,海外房地产网站建设猫猫和企鹅
题目传送门
题目描述
王国里有 n n n 个居住区#xff0c;它们之间有 n − 1 n-1 n−1 条道路相连#xff0c;并且保证从每个居住区出发都可以到达任何一个居住区#xff0c;并且每条道路的长度都为 1 1 1。
除 1 1 1 号居住区外#xff0c;每个居住区住…猫猫和企鹅
题目传送门
题目描述
王国里有 n n n 个居住区它们之间有 n − 1 n-1 n−1 条道路相连并且保证从每个居住区出发都可以到达任何一个居住区并且每条道路的长度都为 1 1 1。
除 1 1 1 号居住区外每个居住区住着一个小企鹅有一天一只猫猫从 1 1 1 号居住区出发想要去拜访一些小企鹅。可是猫猫非常的懒它只愿意去距离它在 d d d 以内的小企鹅们。
猫猫非常的懒因此希望你告诉他他可以拜访多少只小企鹅。
输入格式
第一行两个整数 n , d n, d n,d意义如题所述。
第二行开始共 n − 1 n - 1 n−1 行每行两个整数 u , v u, v u,v表示居民区 u u u 和 v v v 之间存在道路。
输出格式
一行一个整数表示猫猫可以拜访多少只小企鹅。
样例 #1
样例输入 #1
5 1
1 2
1 3
2 4
3 5样例输出 #1
2提示
对于 100 % 100\% 100% 的数据满足 1 ≤ n , d ≤ 1 0 5 1 \le n ,d \le 10^5 1≤n,d≤105保证所有居民区从 1 1 1 开始标号。
以下是本人的想法我一开始利用的是树的重心的算法模板但是之前用for(int i h[now]; i ! -1; i ne[i])时输不出结果最后将当中的“i -1”改成“i”就过了有大佬能告诉我这两种链表的用法吗
#includeiostream
#includealgorithm
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;
}
