当前位置: 首页 > news >正文

洛谷P5908 猫猫和企鹅 做题反思(2024.3.7)

猫猫和企鹅

题目传送门

题目描述

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

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

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

输入格式

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

第二行开始,共 n − 1 n - 1 n1 行,每行两个整数 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 1n,d105,保证所有居民区从 1 1 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;
}

相关文章:

洛谷P5908 猫猫和企鹅 做题反思(2024.3.7)

猫猫和企鹅 题目传送门 题目描述 王国里有 n n n 个居住区&#xff0c;它们之间有 n − 1 n-1 n−1 条道路相连&#xff0c;并且保证从每个居住区出发都可以到达任何一个居住区&#xff0c;并且每条道路的长度都为 1 1 1。 除 1 1 1 号居住区外&#xff0c;每个居住区住…...

常见的验证码

一、短信验证码 前端&#xff1a; 用户填写手机号&#xff0c;点击按钮发送请求用户短信得到验证码后&#xff0c;用户填写表单提交 form 表单&#xff0c;进行验证 后台&#xff1a; 随机生成几位验证码并将生成时间、手机号、验证码存储起来&#xff0c;可以存到session、…...

11. C语言标准函数库

C语言制定了一组使用方式通用的函数&#xff0c;称为C语言标准函数库&#xff0c;用于实现编程常用功能&#xff0c;标准函数库由编译器系统提供&#xff0c;并按功能分类存储在不同源代码文件中&#xff0c;调用标准库内函数时需要首先使用 #include 连接对应的源代码文件。 【…...

2016年认证杯SPSSPRO杯数学建模C题(第一阶段)如何有效的抑制校园霸凌事件的发生解题全过程文档及程序

2016年认证杯SPSSPRO杯数学建模 C题 如何有效的抑制校园霸凌事件的发生 原题再现&#xff1a; 近年来&#xff0c;我国发生的多起校园霸凌事件在媒体的报道下引发了许多国人的关注。霸凌事件对学生身体和精神上的影响是极为严重而长远的&#xff0c;因此对于这些情况我们应该…...

设计模式-抽象工厂模式实践案例

抽象工厂模式&#xff08;Abstract Factory Pattern&#xff09;是一种创建型设计模式&#xff0c;它提供了一个接口&#xff0c;用于创建一系列相关或相互依赖的对象&#xff0c;而无需指定它们具体的类。抽象工厂模式是围绕一个超级工厂创建其他工厂的模式。该模式的实现涉及…...

用readproc函数读取进程的状态

概要&#xff1a; 本篇演示用readproc函数读取进程的状态 libprocps库的安装参考笔者的文章readproc.h-CSDN博客 演示所用的系统是Ubuntu22.04 一、代码 #include<stdio.h> #include<stdlib.h> #include<proc/readproc.h> int main() {struct PROCTAB *…...

在高并发、高性能、高可用 三高项目中如何设计适合实际业务场景的分布式id(一)

分布式ID组件&#xff1a;黄金链路上的关键基石 在现代分布式系统中&#xff0c;分布式ID组件无疑扮演着至关重要的角色。作为整个系统的黄金链路上的关键组件&#xff0c;它的稳定性和可靠性直接关乎到整个系统的正常运作。一旦分布式ID组件出现问题&#xff0c;黄金链路上的…...

redis最新版本在Windows系统上的安装

一、说明 这次安装操作主要是根据redis官网说明&#xff0c;一步步安装下来的&#xff0c;英语比较好的同学&#xff0c;可以直接看文章底部的超链接1&#xff0c;跳到官网按步操作即可。 目前redis的最新稳定版本为redis7.2。 二、Windows环境改造 Redis在Windows上不被官方…...

【深度优先】【图论】【C++算法】2045. 到达目的地的第二短时间

作者推荐 视频算法专题 LeetCode2045. 到达目的地的第二短时间 城市用一个 双向连通 图表示&#xff0c;图中有 n 个节点&#xff0c;从 1 到 n 编号&#xff08;包含 1 和 n&#xff09;。图中的边用一个二维整数数组 edges 表示&#xff0c;其中每个 edges[i] [ui, vi] 表…...

思维题(蓝桥杯 填空题 C++)

目录 题目一&#xff1a; ​编辑 代码&#xff1a; 题目二&#xff1a; 代码&#xff1a; 题目三&#xff1a; 代码&#xff1a; 题目四&#xff1a; 代码&#xff1a; 题目五&#xff1a; 代码&#xff1a; 题目六&#xff1a; 代码七&#xff1a; 题目八&#x…...

Meta的Llama2模型已上线!但我为何更推荐你从HuggingFace获取?还有Code Llama等你来解锁!

嘿&#xff0c;朋友们&#xff0c;今天给你们介绍一个新东西——Llama2模型&#xff0c;这是Meta&#xff08;对&#xff0c;就是Facebook那家&#xff09;推出的。 你可以直接去Llama的官网下载这个模型&#xff0c;然后按照他们GitHub上的指南来调用。 不过呢&#xff0c;我…...

CAN总线及通讯的工作原理

一、CAN总线 CAN是控制器局域网络(Controller Area Network)的简称&#xff0c; 它是由研发和生产汽车电子产品著称的德国BOSCH公司开发的&#xff0c; 并最终成为国际标准&#xff08;ISO11519&#xff09;&#xff0c;是国际上应用最广泛的现场总线之一。 二、工作原理 …...

linux下修改网卡MAC地址

我建议你使用 macchanger&#xff0c;但如果你不想使用它&#xff0c;那么可以使用另一种方法在 Linux 中更改 MAC 地址。 首先&#xff0c;使用以下命令关闭网卡&#xff1a; sudo ip link set dev enp0s31f6 down 接下来&#xff0c;使用以下命令设置新的 MAC&#xff1a;…...

47、WEB攻防——通用漏洞Java反序列化EXP生成数据提取组件安全

文章目录 序列化和反序列化的概念&#xff1a; 序列化&#xff1a;把java对象转换成字节流的过程&#xff1b;反序列化&#xff1a;把字节流恢复为java对象的过程。 对象的序列化主要有两种用途&#xff1a; 把对象的字节流永久的保存在硬盘上&#xff0c;通常存放在一个文件…...

phpstorm console xdebug

1.所有配置跟浏览器http请求一样 2.记得Current File 必须是controller文件 注意&#xff1a;如果没有出发断点&#xff0c;则echo phpinfo(),查看remote_port 和phpstorm 配置是否对上。...

Vue template到render过程

Vue template到render过程 vue的模版编译过程主要如下&#xff1a;template -> ast -> render函数&#xff08;1&#xff09;调用parse方法将template转化为ast&#xff08;抽象语法树&#xff09;&#xff08;2&#xff09;对静态节点做优化&#xff08;3&#xff09;生…...

【你也能从零基础学会网站开发】Web建站之HTML+CSS入门篇 CSS常用属性

&#x1f680; 个人主页 极客小俊 ✍&#x1f3fb; 作者简介&#xff1a;web开发者、设计师、技术分享 &#x1f40b; 希望大家多多支持, 我们一起学习和进步&#xff01; &#x1f3c5; 欢迎评论 ❤️点赞&#x1f4ac;评论 &#x1f4c2;收藏 &#x1f4c2;加关注 CSS常用属性…...

Golang 写日志到文件

package mainimport ("log""os""time" )func main() {printLog("auto", "报警内容AA") }func printLog(filename string, content string) {t : time.Now().Format(time.DateOnly)file : filename "." t "…...

数字孪生10个技术栈:数据处理的六步骤,以获得可靠数据。

一、什么是数据处理 在数字孪生中&#xff0c;数据处理是指对采集到的实时或历史数据进行整理、清洗、分析和转化的过程。数据处理是数字孪生的基础&#xff0c;它将原始数据转化为有意义的信息&#xff0c;用于模型构建、仿真和决策支持。 数据处理是为了提高数据质量、整合数…...

运维随录实战(5)之centos搭建jenkins

一,搭建jenkins准备 下载安装jdk环境 -》版本 jdk11 下载安装maven环境 -》版本 maven 3.8.8 git -》版本 1.8.3.1 yum install git jenkins安装版本:2.414.3 下载地址:https://get.jenkins.io/war-stable/2.414.3/jenkins.war 注:jenkins版本与jdk版本有一定的对应关…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...