当前位置: 首页 > 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版本有一定的对应关…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...