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

树的直径 (dp或贪心)

news 来源：原创 2025/9/18 11:00:30

B4016 树的直径 - 洛谷

题目大意：

给定一棵 n 个结点的树，树没有边权。请求出树的直径是多少，即树上的最长路径长度是多少。

思路：

树形 $d p$ 求树的直径

定义 $d [x]$ 表示以 $x$ 节点出发走向 $x$ 的子树，能到达的最远距离，

接下来只需要考虑对每个 $x$ 节点求出经过 $x$ 节点的最长链即可，

定义 $f [x]$ 表示经过 $x$ 节点的最长链，

考虑转移， $d [x]$ 只需先 $df s$ 到叶子节点，再由下向上更新即可

void dfs(int u,int fa){for(auto x:g[u]){if(x==fa) continue;dfs(x,u);d[u]=max(d[u],d[x]+1);}
}

$f [x]$ 只需考虑 $x$ 节点能够到达的两个最远节点 $y_i$ 的 $d[y_i]$ 即可，

而在更新 $d [x]$ 的时候，每次都会保存一个最大的节点，因此更新 $f [x]$ 时，只需考虑 $d [x]$ 中保存最大的与要更新的路径求 $ma x$ 即可

void dfs(int u,int fa){for(auto x:g[u]){if(x==fa) continue;dfs(x,u);f[u]=max(f[u],d[u]+d[x]+1);d[u]=max(d[u],d[x]+1);}	
}

两边 $df s$ 贪心求直径

从任意一个节点出发， $df s$ 遍历到这个点最远能够到达的点，这个点一定是直径上的点，如果不是直径上的点，那么一定存在一个点比这个点更优

第二次以直径上的点 $df s$ 求一遍最大值即可

void dfs(int u,int fa){for(auto x:g[u]){if(x==fa) continue;d[x]=d[u]+1;if(d[x]>ans){ans=d[x];pos=x;}dfs(x,u);}	
}

代码1（树形 $d p$ ）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define lowbit(x) x&-x
#define ALL(x) x.begin(),x.end()const int mod = 1e9 + 7;
const int N = 1e5+10;int d[N],f[N];
int n;
vector<int> g[N];void dfs(int u,int fa) {for(auto x:g[u]){if(x==fa) continue;dfs(x,u);f[u]=max(f[u],d[u]+d[x]+1);d[u]=max(d[u],d[x]+1);}
}void solve() {int n;cin>>n;for(int i=2;i<=n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);int ans=0;for(int i=1;i<=n;i++){ans=max(ans,f[i]);}cout<<ans; 
}signed main() {std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T = 1;
//	cin >> T;while (T--) {solve();}return 0;
}

代码2（贪心 $df s$ ）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define lowbit(x) x&-x
#define ALL(x) x.begin(),x.end()const int mod = 1e9 + 7;
const int N = 1e5+10;int d[N],f[N];
int n;
vector<int> g[N];
int ans,pos;void dfs(int u,int fa) {for(auto x:g[u]){if(x==fa) continue;d[x]=d[u]+1;if(d[x]>ans){ans=d[x];pos=x;}dfs(x,u);}
}void solve() {int n;cin>>n;for(int i=2;i<=n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}d[1]=0;dfs(1,0);d[pos]=0;ans=0;dfs(pos,0);cout<<ans; 
}signed main() {std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T = 1;
//	cin >> T;while (T--) {solve();}return 0;
}

树的直径 (dp或贪心)

B4016 树的直径 - 洛谷题目大意： 给定一棵 n 个结点的树，树没有边权。请求出树的直径是多少，即树上的最长路径长度是多少。思路： 树形 d p dp dp 求树的直径定义 d [ x ] d[x] d[x] 表示以 x x x 节点出发走向 x x x 的…...

编程日记 2025/9/18 11:00:30

C++ 入门二：C++ 编程预备知识

一、使用 Qt Creator 创建 C 工程 1.1 打开软件在计算机中找到 Qt Creator 的应用程序图标并双击打开它。如果是首次打开，可能需要进行一些初始化设置，如选择默认的开发环境等。 1.2 选择 C 工程打开 Qt Creator 后，在欢迎界面中点击 “…...

编程日记 2025/9/9 20:05:21

IT管理思路

甲方CIO和IT管理者-如何做好组织级IT能力提升_哔哩哔哩_bilibili...

编程日记 2025/9/15 21:46:41

C++17模板编程与if constexpr深度解析

一、原理深化 1.1 模板编程 1.1.1 编译器如何处理模板（补充） 模板的实例化机制存在两种模式： 隐式实例化：编译器在遇到模板具体使用时自动生成代码，可能导致多翻译单元重复实例化，增加编译时间。显式实…...

编程日记 2025/9/8 6:49:16

指令层级：训练大型语言模型优先处理特权指令

指令层级：训练大型语言模型优先处理特权指令 The Instruction Hierarchy: Training LLMs to Prioritize Privileged Instructions关键要点：快速浏览：1. 引言（Introduction）2. 指令层级（The Instruction Hie…...

编程日记 2025/9/18 11:00:29

高效人脸关键点检测算法HRNet-Facial-Landmark-Detection

高效人脸关键点检测算法HRNet-Facial-Landmark-Detection 300 W data 数据标注格式 helen/trainset/1271089376_2.jpg,2.105,642.5,643.5,453.88947199999996,562.431791,457.882374,607.338625,471.39681399999995,655.136824,489.458724,702.023327,508.36972599999996,743.…...

编程日记 2025/9/18 10:57:55

LeetCode 3375 题解

题解如题所示，允许暴力，虽然是暴力，但复杂度也就O(n) 还是如昨天的题目一样，使用Set.add的方法去判断即可分三种情况因为是set集合的原因，所以可以排除值相同的原因当遍历数组有值小于k就return -1 当遍历数组遇…...

编程日记 2025/9/10 15:16:42

leetcode_数组 189. 轮转数组

189. 轮转数组给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数示例 1: 输入: nums [1,2,3,4,5,6,7], k 3输出: [5,6,7,1,2,3,4] 示例 2: 输入：nums [-1,-100,3,99], k 2输出：[3,99,-1,-100] 思…...

编程日记 2025/9/8 0:50:51

MySQL | 三大日志文件

Undo Log（回滚日志） 实现原理与分类原理：Undo Log 记录的是数据修改前的旧值，通过这些旧值可以将数据恢复到修改之前的状态。它采用的是逻辑日志，即记录的是如何撤销操作，而不是物理数据的实际值。分类…...

编程日记 2025/9/15 0:08:19

GIS-AI 融合引擎架构：智慧景区导览系统的毫秒级响应与千级并发优化实战

本文面向文旅行业技术决策者、GIS 开发者、AI 算法工程师，旨在解决传统景区导览系统定位精度低、交互体验差、运营成本高的核心痛点，提供从技术选型到落地部署的全链路解决方案。如需获取智慧景区导览系统解决方案请前往文章最下方获取，如…...

编程日记 2025/9/18 10:57:56

WSA（Windows 安卓子系统）过检测教程

windows安卓子系统WSA的root和magisk的安装教程安卓子系统WSLWSA的rootmagisk安装 WSA（Windows 安卓子系统）过检测的方法与思路一、引言 Windows 安卓子系统（WSA）为 Windows 用户提供了在电脑上运行安卓应用的便利。然而&…...

编程日记 2025/9/18 10:57:08

Spark原理及代码

一、 Spark运行架构运行架构 Spark 框架的核心是一个计算引擎，整体来说，它采用了标准 master-slave 的结构。 Spark 框架有两个核心组件： 1、Driver Spark 驱动器节点，用于执行 Spark 任务中的 main 方法，负责实…...

编程日记 2025/9/17 2:05:43

esp32cam -＞服务器 | 手机 -＞服务器直接服务器传输图片

服务器先下载python ： 一、Python环境搭建（CentOS/Ubuntu通用） 一条一条执行安装基础依赖 # CentOS sudo yum install gcc openssl-devel bzip2-devel libffi-devel zlib-devel # Ubuntu sudo apt update && sudo apt install b…...

编程日记 2025/9/18 10:55:52

RHCSA Linux系统数据流和重定向 tee 命令

一.数据流和重定向 1. 数据流 (1) 标准输入（stdin，代码 0）：默认从键盘获取输入，只读。 (2) 标准输出（stdout，代码 1）：命令执行正确信息默认输出到屏幕，只写…...

编程日记 2025/9/9 17:53:53

libev实现Io复用及定时器事件服务器

客户端和服务器都绑定在了enp2s0网卡，需要SERVER_IP和SERVER_PORT改为其ip，注意不能是127.0.0.1，因为这个是lo虚拟网口。安装libev sudo apt-get install libev-dev客户端： #include <iostream> #include <string>…...

编程日记 2025/9/6 12:58:37

【项目实训项目博客】prompt初版实践

通过对camel技术的理解，我们向其中添加了市场营销角色的prompt 初版设计如下： chatchainconfig.json { "chain": [ { "phase": "DemandAnalysis", "phaseType": "SimplePhase", "max_turn_step…...

编程日记 2025/9/18 10:57:08

底盘---全向轮(Omni Wheel)

一、基本定义与起源定义： 全向轮是一种通过在主轮外周安装多个垂直于主轮轴线的横向小滚轮实现多向移动的轮式结构。小滚轮可自由转动，允许设备在纵向（主轮驱动方向）和横向（小滚轮滚动方向）同时受力&…...

编程日记 2025/9/15 7:23:46

Python标准库json完全指南：高效处理JSON数据

一、json库概述 JSON(JavaScript Object Notation)是一种轻量级的数据交换格式，Python的json模块提供了JSON数据的编码和解码功能。该模块可以将Python对象转换为JSON字符串（序列化），也可以将JSON字符串转换为Python对象&#xf…...

编程日记 2025/9/11 13:10:47

用一个实际例子快速理解MCP应用的工作步骤

已经有很多的文章介绍MCP server，MCP Client工作原理，这里不做太多介绍。但是很多介绍都只是侧重介绍概念，实际的工作原理理解起来对初学者还是不太友好。本文以一个智能旅游咨询系统为例，详细说明在利用 Model Context Protocol&…...

编程日记 2025/9/15 8:10:23

Element Plus 图标使用方式整理

Element Plus 图标使用方式整理以下是 Element Plus 图标的所有使用方式，包含完整代码示例和总结表格： 1. 按需引入图标组件适用场景：仅需少量图标时，按需导入减少打包体积示例代码： <template><div>…...

编程日记 2025/9/10 15:31:19

力扣题解：142. 环形链表 II

在链表学习中，我们已经了解了单链表和双链表，两者的最后一个结点都会指向NULL；今天我们介绍的循环列表则不同，其末尾结点指向的这是链表中的一个结点。循环链表是一种特殊类型的链表，其尾节点的指针指向头节点&#…...

编程日记 2025/9/18 1:45:28

图灵逆向——题七-千山鸟飞绝

目录列表过程分析headers头部M参数分析载荷x参数分析响应数据解密分析代码实现一进来还是一个无限debugger，前面有讲怎么过，这里直接过掉~ 老规矩，养成习惯，先看请求头里有没有加密参数发现好像是有个M，它是个32位…...

编程日记 2025/9/15 23:36:52

双相机结合halcon的条码检测

以下是针对提供的C#代码的详细注释和解释，结合Halcon库的功能和代码结构进行说明： --- ### **代码整体结构** 该代码是一个基于Halcon库的条码扫描类GeneralBarcodeScan，支持单台或双台相机的条码检测，并通过回调接口返回结果。…...

编程日记 2025/9/12 5:18:48

Transformer Decoder Block的几个优化方案

写在前面在大型语言模型（LLM）的演进浪潮中，Transformer 架构凭借其强大的并行计算能力和对长距离依赖的出色捕捉，奠定了核心地位。然而，标准的 Transformer Decoder Block 遵循着一种相对固定的模式：先进行自注意力（Self-Attention）捕捉上下文信息，再通过前馈神经网…...

编程日记 2025/9/16 1:58:35

工业科学级天文相机：跨界融合的高精密成像解决方案

随着国内科技的快速发展，工业相机领域正悄然兴起一场"天文级"的技术革命。这类兼具工业设备可靠性与天文观测精度的特殊相机，正在半导体制造、天文观测、空间探测等领域开辟新的应用疆域。其核心技术突破不仅体现在传感器性能的提升&#xff0…...

编程日记 2025/9/17 16:16:08

颠覆传统！复旦微软联合研发MagicMotion，重新定义图生视频可能性

导读简介： 尽管基于DiT的模型在生成高质量和长视频方面表现出色，但许多文本到视频的方法在精确控制物体运动和相机运动等属性方面存在不足。因此，细粒度轨迹可控的视频生成技术应运而生，这对于在现实场景中生成可控视频至关重要。…...

编程日记 2025/9/13 3:33:01

华为数字芯片机考2025合集5已校正

1. 题目内容下列选项中（）不是 Verilog HDL 的关键字。（） A. tri B. for C. force D. edge 解析 1. Verilog 关键字分类 Verilog 关键字是语言预定义的保留字，用于语法结构或特定功能。 2. 选项分析选项类型说明…...

编程日记 2025/9/12 16:15:23

QML Loader：延迟加载与动态切换

目录引言相关阅读工程结构LoaderDelay.qml - 延迟加载实现完整代码HeavyComponent.qml代码解析运行效果 LoaderSwitch.qml - 动态切换组件完整代码代码解析运行效果 Main.qml - 主界面实现完整代码主界面结构代码解析总结下载链接引言 QML的Loader组件提供了一种强大的机制…...

编程日记 2025/9/11 11:18:16

C语言--常用的链表操作

利用C语言实现链表，并定义一些常用的操作文章目录链表定义新建一个链表结点打印链表插入结点头插法（常用）运行尾插法（使用较少）运行返回链表长度链表转置运行合并两个有序的链表运行删除最小结点运行打印倒数第…...

编程日记 2025/9/13 18:10:54

ngx_conf_param

Ubuntu 下 nginx-1.24.0 源码分析 - ngx_conf_param-CSDN博客定义在 src\core\ngx_conf_file.c char * ngx_conf_param(ngx_conf_t *cf) {char *rv;ngx_str_t *param;ngx_buf_t b;ngx_conf_file_t conf_file;param &cf->cycle->conf…...

编程日记 2025/9/15 14:51:52

C++day9

思维导图牛客练习练习： 将我们写的 myList 迭代器里面 operator[] 和 operator 配合异常再写一遍 #include <iostream> #include <cstring> #include <cstdlib> #include <unistd.h> #include <sstream> #include <vector>…...

编程日记 2025/9/13 7:32:04

算法题：两数相加

题目：2. 两数相加给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外&a…...

编程日记 2025/9/9 1:33:09

SCI科学论文的重要组成部分

科学论文的核心结构科学论文通常遵循IMRAD结构，即： 引言(Introduction)方法(Methods)结果(Results)讨论(Discussion) 除此之外，还包括其他几个关键部分。让我为您详细介绍每个部分的作用和重要性： 1. 标题(Title) 标题是论文…...

编程日记 2025/9/13 15:37:01

Go 微服务框架 | 路由实现

文章目录不用框架实现web接口实现简单的路由实现分组路由支持不同的请求方式支持同一个路径的不同请求方式前缀树应用前缀树完善路由代码不用框架实现web接口 // blog main.go 文件 package mainimport ("fmt""log""net/http" )func main() {…...

编程日记 2025/9/16 3:38:52

2025年AI开发学习路线

目录一、基础阶段（2-3个月） 1. 数学与编程基础 2. 机器学习入门二、核心技能（3-4个月） 1. 深度学习与框架 2. 大模型开发（重点） 三、进阶方向（3-6个月） 1. 多模态与智能体…...

编程日记 2025/9/13 18:49:10

TimescaleDB 2.19.2 发布

TimescaleDB 2.19.2 已于 2025 年 4 月 7 日发布2。此次发布是基于 PostgreSQL 的开源时序数据库 TimescaleDB 的一次更新。从 GitHub 上的 Pull Request 信息可知，此次发布主要是将相关更改合并到 2.19.x 分支，涉及到一系列的测试和构建配置，包括不同版本 PostgreSQL（如 …...

编程日记 2025/9/11 3:55:00

「Unity3D」TextMeshPro中的TMP_InputField，用来实现输入框的几个小问题

第一，正确设置Scrollbar。设置Scrollbar之后，不能设置Text Component的Font Size为Auto Size，否则Scrollbar无法正确计算显示。那么，要想自动适配字体大小，可以让Placeholder中的Font Size设置为Auto，这…...

编程日记 2025/9/8 21:42:50

HTML 是什么？网页创建的核心标记语言

原文：HTML 是什么？网页创建的核心标记语言 | w3cschool笔记 HTML 是什么？ HTML 是一种标记语言，用于创建网页。简单来说，HTML 就像一本魔法书，它告诉电脑如何展示网页上的内容，比如文字、图片…...

编程日记 2025/9/10 20:15:27

考研单词笔记 2025.04.09

act v表现，行动，做事，扮演，充当，担任，起作用n行为，行动，法案，法令 action n行为，行动 behave v表现，行事，守规矩，举止端…...

编程日记 2025/9/7 22:25:34

map/multimap

1.概念 map中所有元素都是pair<key,value>，key 是map的键，value 是map的值所有元素都会根据key自动排序 map/multimap属于关联式容器，底层结构是用二叉树实现。 map和multimap区别： map不允许容器中有重复key值元素 m…...

编程日记 2025/9/12 12:57:10

CSS 定位属性的生动比喻：以排队为例理解 relative 与 absolute

目录一、理解标准流与队伍的类比二、relative 定位：队伍中 “小范围活动” 的人三、absolute 定位：队伍中 “彻底离队” 的人在学习 CSS 的过程中，定位属性relative和absolute常常让初学者感到困惑。它们的行为方式和对页面布局的影响较…...

编程日记 2025/8/28 3:46:32

基于二叉堆实现的 PriorityQueue

基于二叉堆实现的 PriorityQueue 是一种常见的数据结构，广泛用于任务调度、路径搜索、事件模拟等场景。下面我将用 Java 语言实现一个简单的基于最小堆的 PriorityQueue，即优先级最小的元素先出队。 ✅ 实现目标使用数组实现二叉最小堆（即父…...

编程日记 2025/9/15 0:28:28

大模型分布式推理和量化部署

一、小常识 1、计算大模型占用多少显存对于一个7B（70亿）参数的模型，每个参数使用16位浮点数（等于 2个 Byte）表示，则模型的权重大小约为： 7010^9 parameters2 Bytes/parameter14GB 70亿个参数…...

编程日记 2025/9/14 18:03:53

循环神经网络 - 长程依赖问题及改进方案

循环神经网络在学习过程中的主要问题是由于梯度消失或爆炸问题，很难建模长时间间隔(Long Range)的状态之间的依赖关系。本文我们来学习长程依赖问题及其对应的改进方案，在这部分知识的学习过程中，我建议大家着重理解，对于数学公…...

编程日记 2025/9/16 3:45:51

点击抽奖功能总结

首先用户打开网页，映入眼帘的是一个输入框和一个提交按钮。当用户在输入框中输入自己的年龄并点击提交后，系统会根据输入的年龄给出相应提示。若年龄达到 60 岁，页面将显示一个新的抽奖区域，用户可以点击 “抽奖” 按钮开始抽奖。…...

编程日记 2025/9/15 23:52:52

AWS Bedrock生成视频详解：AI视频创作新时代已来临

💡 TL;DR: AWS Bedrock现已支持AI视频生成功能，让企业无需深厚AI专业知识即可创建高质量视频内容。本文详解Bedrock视频生成能力的工作原理、应用场景和实操指南，助你快速掌握这一革命性技术。 🎬 AWS Bedrock视频生成：改变内容创作的游戏规则还记得几年前，制作一个专…...

编程日记 2025/9/16 7:15:16

理解 TOGAF®标准中的架构原则

原则是帮助组织实现其使命的基本规则和指南。它们旨在长期稳定且很少修改，在各个领域中充当决策和行动的指南针。在企业架构（EA）的背景下，原则在指导架构框架的开发和应用方面发挥着至关重要的作用。本文将探讨企业原则和架构原则…...

编程日记 2025/9/11 3:16:40

基于视觉密码的加密二值图像可逆数据隐藏

接下来，分享一篇论文，标题为《Multi-Party Reversible Data Hiding in Ciphertext Binary Images Based on Visual Cryptography》，由Bing Chen等人发表在《IEEE Signal Processing Letters》上。该论文提出了一种基于视觉密码学的多方可逆数…...

编程日记 2025/9/18 10:50:13

ubuntu22.04 中 No module named ‘_bz2‘问题解决方案

前言本篇是介绍ubuntu22.04中 No module named ‘_bz2‘问题解决方案网上版本很多，比如安装libbz库什么的，可能别人有用，但是我自己这边出了一堆问题一、流程 1.1 查看bz2.xx.so文件看自己的python版本，我新安装了个pyth…...

编程日记 2025/9/11 11:35:35

什么是声波，声波的传播距离受哪些因素影响？

一、声波的定义： 声波是一种机械波，它是通过介质（如空气、水、固体等）传播的振动。以下是关于声波的详细介绍： 1、声波的产生声波是由物体的振动产生的。例如，人说话时，声带振动产生声波&…...

编程日记 2025/8/29 21:39:24

相关文章：