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

树的直径 | 树的最长路径

news 来源：原创 2025/6/28 23:35:33

树的直径：

树上任意两节点之间最长的简单路径即为树的「直径」。

定理：

在一棵树上，从任意节点 u 开始进行一次 DFS，到达的距离其最远的节点 v 必为直径的一端。

B4016 树的直径 - 洛谷

思路：

由于这题中每条边的权值都为 1，因此可以直接使用定理来解决

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvector<vector<int>> g(100005);pair<int,int> dfs(int s,int f)
{pair<int, int> res = {s,1};for (auto son : g[s]){if (son == f)continue;auto sr = dfs(son, s);if (sr.second + 1 > res.second){res.second = sr.second + 1;res.first = sr.first;}}return res;
}void solve()
{int n;cin >> n;for (int i = 0; i < n-1; i++){int x, y; cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}auto root = dfs(1,1);auto res = dfs(root.first, root.first);cout << res.second - 1;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

U309522 树的最长路径 - 洛谷

思路：

这一题的边的权值不一样，倘若有负边的话我们无法使用定理来做，那我们可以考虑树形dp（虽然这题没有负边）

我们定义 d1 d2 为每个节点往后延申的最长路径和次最长路径，为什么要存储 d2 呢？因为可能存在以另外一个节点为根节点时的最长路径为 d1 + d2，我们默认根节点为 1 ，所以没考虑上述情况，所以应该存个次最长，然后在 dfs 中时刻存储最大长度即可

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvector<vector<pair<int,int>>> g(10005);
int res = 0;
int dfs(int self,int fa)
{int d1 = 0, d2 = 0;for (auto son : g[self]){if (son.first == fa)continue;int d = (dfs(son.first, self) + son.second);if (d > d1){d2 = d1;d1 = d;}else if (d > d2){d2 = d;}}res = max(res, d1 + d2);return d1;
}void solve()
{int n;cin >> n;for (int i = 0; i < n-1; i++){int u, v, a;cin >> u >> v >> a;g[u].push_back({ v,a });g[v].push_back({ u,a });}dfs(1, 1);cout << res << endl;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

树的直径 | 树的最长路径

树的直径： 树上任意两节点之间最长的简单路径即为树的「直径」。定理： 在一棵树上，从任意节点 u 开始进行一次 DFS，到达的距离其最远的节点 v 必为直径的一端。 B4016 树的直径 - 洛谷思路： 由于这题中每条边的…...

编程日记 2025/6/28 23:35:33

AbMole解读：脂质体的关键组分和主要合成方法

脂质体（Liposome）是一种由磷脂等两性分子自发形成的封闭囊泡结构，随着纳米技术、材料科学等多学科的交叉发展，脂质体的研究与应用进入了一个新的阶段，并在肿瘤研究、疫苗研发、基因递送等多个领域发挥着关键作用。AbMo…...

编程日记 2025/6/28 22:53:22

Python爬虫之品牌口碑数据抓取

上一篇我们介绍了爬虫营销的优势，这次我就展开详细的说说，如何通过爬取社交媒体或电商平台的公开评论来分析自己或竞争对手的品牌声誉。选择微博这样的平台，因为它的数据相对公开，而且有API支持，但要注意频率限制和反…...

编程日记 2025/6/29 14:45:58

【android bluetooth 协议分析 12】【A2DP详解 1】【车机侧蓝牙音乐免切源介绍】

“车机蓝牙音乐免切源” 是近年来车载系统（IVI，In-Vehicle Infotainment）中常见的一个用户体验优化功能。它主要是为了简化蓝牙音乐播放流程、减少用户操作，提升使用便捷性。一、什么是“切源”？ 在车机系统中&#…...

编程日记 2025/6/29 0:11:44

眼镜店哪个品牌好,你会选择哪一款眼镜

有些人买眼睛是为了耍帅，有些人买眼镜，可能就是为了调节视力。现在手机以及其他的电子产品越来越普及，近视眼的人群是越来越多了，那么要准备去配眼镜的话，就要找到一个正规的眼镜店，一起来了解一下眼镜店哪…...

编程日记 2025/6/28 23:13:36

基于EFISH-SCB-RK3576/SAIL-RK3576的畜禽养殖监控仪技术方案‌

（国产化替代J1900的农业物联网解决方案） 一、硬件架构设计‌ ‌多源环境感知模块‌ ‌空气质量监测‌： 集成NH₃/CO₂/H₂S三合一气体传感器（量程0-500ppm，精度2%FS），采样间隔≤1秒激光粉尘检测…...

编程日记 2025/6/28 16:45:43

linux - 权限的概念

目录用户权限超级用户与普通用户的区别超级用户（root）： 普通用户： 切换用户身份使用sudo执行高权限命令用户管理用户组管理文件权限文件访问者类别基本权限权限表示方法权限修改 chmod chown chgrp u…...

编程日记 2025/6/28 22:53:24

LeRobot 框架的核心架构概念和组件（中）

本文档概述构成 LeRobot 框架的核心架构概念和组件。它介绍主要的子系统，并解释它们如何相互作用以实现机器人学习。。。。。。。继续。。。。。。环境接口环境系统提供与模拟环境交互的统一接口。这些环境允许在部署到物理机器人之前，在受控环境中…...

编程日记 2025/6/28 23:07:31

鸿蒙5.0项目开发——鸿蒙天气项目的实现（主页1）

【高心星出品】文章目录页面效果：页面功能：页面执行流程：1. 页面初始化阶段2. 定位获取阶段3. 天气数据加载阶段这个页面是整个天气应用的核心，集成了天气查询、定位、搜索等主要功能，提供了完整的天气信息服务。 …...

编程日记 2025/6/29 0:52:57

虚幻引擎5-Unreal Engine笔记之摄像机与场景捕获相关概念的解析

虚幻引擎5-Unreal Engine笔记之摄像机与场景捕获相关概念的解析 code review! 文章目录虚幻引擎5-Unreal Engine笔记之摄像机与场景捕获相关概念的解析1. UE中SceneCapture和UCameraComponent的关系是什么？Camera和SceneCapture2D的关系是什么1.1 UCameraComponen…...

编程日记 2025/6/28 22:53:53

【vim】--- vim 插件说明超详细持续更新中

在编程的艺术世界里，代码和灵感需要寻找到最佳的交融点，才能打造出令人为之惊叹的作品。而在这座秋知叶i博客的殿堂里，我们将共同追寻这种完美结合，为未来的世界留下属于我们的独特印记。【vim】--- vim 插件说明超详细持续更新中开发环境一、vim 插件管理器1、Vim-Plug2…...

编程日记 2025/6/28 22:55:04

医学影像系统的集成与工作流优化

🧑 博主简介：CSDN博客专家、CSDN平台优质创作者，高级开发工程师，数学专业，10年以上C/C++, C#, Java等多种编程语言开发经验，拥有高级工程师证书；擅长C/C++、C#等开发语言，熟悉Java常用开发技术，能熟练应用常用数据库SQL server,Oracle,mysql,postgresql等进行开发应用…...

编程日记 2025/6/28 22:53:59

Vue 和 React 状态管理的性能优化策略对比

一、Vue 状态管理优化策略合理使用 Vuex 模块化将全局状态拆分为模块，按需加载，避免单一 Store 文件过大。通过命名空间隔离状态，减少状态冗余和无效更新。 const moduleA { namespaced: true, state: { /* ... */ } }; const store new …...

编程日记 2025/6/29 0:42:58

python打包exe报错：处理文件时错误：Excel xlsx file； not supported

背景：最近用python写一个excel解析工具，然后打包成exe可执行文件的时候，遇到这样的问题 1.在我自己编译器运行是可以正常将上传后的excel进行解析，但是在打包成exe后，就无法正常解析excel 问题排查： 1.切换…...

编程日记 2025/6/28 17:33:38

libmemcached库api接口讲解一

前言：好多接口的用法都不怎么会，得学习一下具体的用法 memcached_st ✅ 一个连接 memcached 服务集群的“客户端实例”对象，用于管理连接、执行读写操作、设置行为、维护哈希环等一切功能。它在使用中通常通过下面的方式创建： …...

编程日记 2025/6/28 22:54:03

【RabbitMQ】发布确认机制的具体实现

文章目录模式介绍建立连接单独确认代码实现逻辑运行结果批量确认代码实现逻辑运行结果异步确认实现逻辑介绍代码实现逻辑运行结果三种策略对比以及完整代码模式介绍作为消息中间件，都会面临消息丢失的问题，消息丢失大概分为三种情况： …...

编程日记 2025/6/29 0:58:07

RabbitMQ是什么？应用场景有哪些？

RabbitMQ 是一款开源的消息代理中间件，基于 AMQP（高级消息队列协议）实现，用于在分布式系统中进行异步通信和消息传递。它通过将消息的发送者和接收者解耦，提高了系统的可扩展性、可靠性和灵活性。核心特点多协议支持：不仅支持 AMQP，还兼容 STOMP、MQTT 等多种消息协议…...

编程日记 2025/6/28 22:54:11

数学实验（Matlab符号运算）

一、符号对象的建立 Matlab符号运算特点计算以推理方式进行，因此不受计算误差积累所带来的困扰符号计算指令的调用比较简单，与数学教科书上的公式相近 Matlab符号运算举例符号对象与符号表达式在进行符号运算时，必须先定义基本的符号…...

编程日记 2025/6/29 0:49:23

使用 hover-class 实现触摸态效果 - uni-app 教程

目录一、什么是 hover-class 二、常用组件支持 hover-class 三、基本效果说明： 四、配合 hover-start-time 和 hover-stay-time 五、注意事项六、实践建议在移动端开发中，良好的用户交互体验尤为重要，点击或长按某个按钮时&#x…...

编程日记 2025/6/28 23:27:28

# 深度剖析LLM的“大脑”：单层Transformer的思考模式探索

简单说一下哈 —— 咱们打算训练一个单层 Transformer 加上稀疏自编码器的小型百万参数大型语言模型（LLM），然后去调试它的思考过程，看看这个 LLM 的思考和人类思考到底有多像。 LLMs 是怎么思考的呢？ 开源 LLM 出现之后…...

编程日记 2025/6/28 22:53:35

Git仓库迁移

前言前面我讲了GitLab搭建与使用(SSH和Docker)两种方式，那么就会延伸出来一个情况：Git仓库迁移虽然这种情况很少发生，但是我自己公司近期要把阿里云迁移到华为云，那么放在上面的Git仓库也要全量迁移下面我就写了一个脚本演示&am…...

编程日记 2025/6/28 22:55:01

Windows避坑部署CosyVoice多语言大语言模型

#工作记录前言在实际部署与应用过程中，项目的运行环境适配性对其稳定性与功能性的发挥至关重要。CosyVoice 项目虽具备强大的语音处理能力，但受限于开发与测试环境的侧重方向，其对运行环境存在特定要求。该项目在 Linux 和 Docker 生态…...

编程日记 2025/6/28 22:53:32

《实现模式》以Golang视角解读价值观和原则 day 1

为什么阅读实现模式？ 为什么阅读《实现模式》？Kent Beck 的《实现模式》其核心思想——编写清晰、易于理解且易于维护的代码，对于软件工程的新手而言，直接深入复杂的设计模式或架构理念可能会感到困惑。《实现模式》则弥合了设计…...

编程日记 2025/6/29 0:20:49

解决 PicGo 上传 GitHub图床及Marp中Github图片编译常见难题指南

[目录] 0.行文概述 1.PicGo图片上传失败 2.*关于在Vscode中Marp图片的编译问题* 3.总结与启示行文概述写作本文的动机是本人看到了Awesome Marp，发现使用 Markdown \texttt{Markdown} Markdown做PPT若加持一些 CSS , JavaScript \texttt{CSS},\texttt{JavaScript} …...

编程日记 2025/6/28 22:53:31

LeetCode 820 单词的压缩编码题解

LeetCode 820 单词的压缩编码题解题目描述题目链接给定一个单词列表，将其编码为一个索引字符串S，格式为"单词1#单词2#…"。要求当某个单词是另一个单词的后缀时，该单词可以被省略。求最终编码字符串的最小长度。解题思路逆…...

编程日记 2025/6/28 22:53:39

Windows软件插件-写wav

下载本插件本插件，将PCM音频流写入WAV音频文件。或将PCM音频流压缩为ALAW格式，写入WAV文件。可以创作大文件（超过4字节所能表示的大小）。插件类型为DLL，可以在win32和MFC程序中使用。使用本插件创建的ALAW格式WAV音频…...

编程日记 2025/6/28 22:53:40

基于 Spring Boot 瑞吉外卖系统开发（十五）

基于 Spring Boot 瑞吉外卖系统开发（十五） 前台用户登录在登录页面输入验证码，单击“登录”按钮，页面会携带输入的手机号和验证码向“/user/login”发起请求。定义UserMapper接口 Mapper public interface UserMapper exte…...

编程日记 2025/6/28 23:13:39

【Linux高级IO】多路转接之epoll

多路复用之epoll 一，认识epoll二，epoll的相关接口1. epoll_create2. epoll_ctl3. epoll_wait 三，epoll的原理四，epoll的两种工作模式（ET和LT）1. 两种工作模式2. 对比ET和LT 五，总结在了解到sel…...

编程日记 2025/6/28 19:42:19

Java 性能调优全解析：从设计模式到 JVM 的 7 大核心方向实践

引言在高并发、低延迟的技术场景中，Java 性能优化需要系统化的方法论支撑。本文基于7 大核心优化方向（复用优化、计算优化、结果集优化、资源冲突优化、算法优化、高效实现、JVM 优化），结合权威框架与真实案例，构建从…...

编程日记 2025/6/29 0:52:34

“海外滴滴”Uber的Arm迁移实录：重构大规模基础设施

云工作负载在性价比上的自然演进路径： Intel ➜ AMD ➜ ARM 不信？来看看 Uber 的做法： 01/Arm架构：云计算新时代 2023 年 2 月，Uber 正式开启了一项战略性迁移：将从本地数据中心迁移至云端，…...

编程日记 2025/6/28 9:31:45

java加强 -File

File类的对象可以代表文件/文件夹，并可以调用其提供的方法对象文件进行操作。 File对象既可以代表文件，也可以代表文件夹。创建File对象，获取某个文件的信息语法： File 对象名 new File("需要访问文件的绝对路径&…...

编程日记 2025/6/28 23:38:58

SQL注入 ---04

1 简单的sql注入要求： 要有sql注入： 1，变量 2，变量要带入数据库进行查询 3，没有对变量进行过滤或者过滤不严谨 mysql> select * from users where id2 limit 0,1; 当我的语句这样写时查寻到的结果当我修改为&…...

编程日记 2025/6/28 22:53:43

MySQL知识点总结（持续更新）

聚合函数通常用于对数据进行统计和聚合操作。以下是一些常见数据库系统（如 MySQL、PostgreSQL、Oracle、SQL Server 等）中常用的聚合函数： 常见的数据库聚合函数： COUNT()：计算指定列中非空值的数量 SELECT COUNT(*) …...

编程日记 2025/6/29 0:01:41

数字信号处理-大实验1.1

MATLAB仿真实验目录验证实验：常见离散信号产生和实现验证实验：离散系统的时域分析应用实验：语音信号的基音周期（频率）测定目录一、常见离散信号产生和实现 1.1 实验目的 1.2 实验要求与内容 1.3 实验…...

编程日记 2025/6/28 22:53:33

Qt操作SQLite数据库教程

Qt 中操作 SQLite 数据库的步骤如下： 1. 添加 SQLite 驱动并打开数据库 #include <QSqlDatabase> #include <QSqlError> #include <QSqlQuery>// 创建数据库连接 QSqlDatabase db QSqlDatabase::addDatabase("QSQLITE"); db.setData…...

编程日记 2025/6/29 0:22:04

【PSINS工具箱】基于工具箱的单独GNSS导航、单独INS导航、两者结合组合导航，三种导航的对比程序。附完整的代码

本文给出基于PSINS工具箱的单独GNSS导航、单独INS导航、两者结合组合导航（153EKF）的程序。并提供三者的轨迹对比、误差对比。文章目录运行结果MATLAB代码代码的简单介绍简介2. 平均绝对误差 (MAE)主要模块运行结果三轴轨迹图：各轴误差曲线：命令行窗口的结果输出： …...

编程日记 2025/6/28 22:55:00

开发者的测试复盘：架构分层测试策略与工具链闭环设计实战

摘要‌ 针对测试复盘流于形式、覆盖率虚高等行业痛点，本文提出一套结合架构分层与工具链闭环的解决方案： ‌分层测试策略精准化‌：通过单元测试精准狙击核心逻辑、契约测试驱动接口稳定性、黄金链路固化端到端场景，实现缺陷拦截率…...

编程日记 2025/6/29 0:02:32

手写CString类

学习和理解字符串处理机制：手写 CString 类是深入学习字符串处理和内存管理的有效方式。通过实现构造函数、析构函数、赋值运算符等，能够理解字符串在内存中的存储方式、动态内存分配和释放的原理，以及如何处理字符串的复制、拼接、查找等操作…...

编程日记 2025/6/29 8:49:46

electron结合vue，直接访问静态文件如何跳转访问路径

在最外的app.vue或者index.vue的js模块编写 let refdade ref(1);//刷新，获得请求// 获取完整的查询字符串（例如: "?dade/myms"）const searchParams new URLSearchParams(window.location.search);// 获取 dade 参数的值&#xf…...

编程日记 2025/6/28 22:53:34

解读RTOS 第七篇 · 驱动框架与中间件集成

1. 引言在面向生产环境的 RTOS 系统中，硬件驱动框架与中间件层是连接底层外设与上层应用的桥梁。一个模块化、可扩展的驱动框架能够简化外设管理，提升代码可维护性；而丰富的中间件生态则为网络通信、文件系统、图形界面、安全加密等功能提供开箱即用的支持。本章将从驱动模…...

编程日记 2025/6/29 0:04:39

Java GUI开发全攻略：Swing、JavaFX与AWT

Swing 界面开发 Swing 是 Java 中用于创建图形用户界面（GUI）的库。它提供了丰富的组件，如按钮、文本框、标签等。 import javax.swing.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener;public class SwingExa…...

编程日记 2025/6/29 0:52:31

Cursor 0.5版本发布，新功能介绍

Cursor，这款流行的AI编程平台，刚刚在其v0.50更新中推出了一系列新功能。首先，请将您的Cursor IDE更新到最新版本。当您打开Cursor时，您应该会在屏幕左下方收到关于最新版本发布的通知。更多上下文控制：对上下文的精细可见性，以及最新模型的MAX模式。聊天升级：导出…...

编程日记 2025/6/28 23:49:36

Android学习总结之Glide自定义三级缓存（实战篇）

一、为什么需要三级缓存内存缓存（Memory Cache） 内存缓存旨在快速显示刚浏览过的图片，例如在滑动列表时来回切换的图片。在 Glide 中，内存缓存使用 LruCache 算法（最近最少使用），能自动清理长…...

编程日记 2025/6/29 1:00:56

Maven 下载安装与配置教程

## 1. Maven 简介 Maven 是一个项目管理和构建自动化工具，主要用于 Java 项目。Maven 可以帮助开发者管理项目的构建、报告和文档，简化项目依赖管理。 ## 2. 下载 Maven 1. 访问 Maven 官方网站 [https://maven.apache.org/download.cgi](https://maven.…...

编程日记 2025/6/28 23:37:07

一篇解决Redis：持久化机制

目录认识持久化持久化方案 RDB（Redis DataBase） 手动触发自动触发小结 AOF(Append-Only File) AOF缓冲区刷新机制 AOF重写机制 AOF重写流程编辑混合持久化认识持久化我们都知道Mysql有四大特征，原子性，持久…...

编程日记 2025/6/29 0:28:04

使用IDEA创建Maven版本的web项目以及lombok的使用

1.新建项目 2.修改pom.xml 3.修改项目结构 4.在main/java下面写一个Servlet测试一下然后当前页面往下滑 -Dfile.encodingUTF-8编写一句输出语句，测试是否成功部署配置，并选择到正确的位置： 回车以后再回到idea里面，发现控…...

编程日记 2025/6/29 0:12:11

2025年AI开发者在开发者占比？

AI开发者在全球开发者中的占比目前没有一个统一且精确的数值，但根据行业报告和调研数据，可以给出以下大致的范围和趋势分析： 1. 综合估算范围全球范围：AI/ML（机器学习）开发者约占开发者总数的 5%-15%&…...

编程日记 2025/6/29 0:11:31

SpringBoot整合MQTT实战：基于EMQX构建高可靠物联网通信，从零到一实现设备云端双向对话

一、引言随着物联网(IoT)技术的快速发展，MQTT(Message Queuing Telemetry Transport)协议因其轻量级、低功耗和高效的特点，已成为物联网设备通信的事实标准。本文将详细介绍如何使用SpringBoot框架整合MQTT协议，基于开源MQTT代理EMQX实现设…...

编程日记 2025/6/28 3:04:06

Windows更新暂停七天关键注册表

环境：windows10 工具：procmon 下载地址：https://learn.microsoft.com/zh-cn/sysinternals/downloads/procmon 监控截图： 界面截图： 注： 1.北京时间差8小时 2.至少是从第二天恢复，即至少暂停…...

编程日记 2025/6/29 1:30:21

小白学习java第18天（上）：spring

Spring ：是一个轻量级（一个小依赖就可以实现还不是轻量级）的控制反转（IOC）和面向切面编程（AOP）的框架！ 优点： 1.Spring 是一个开源免费的框架（容器&#xf…...

编程日记 2025/6/28 23:14:40

B4016 树的直径 - 洛谷

思路：

代码：

U309522 树的最长路径 - 洛谷

思路：

代码：

相关文章：