动态维护直径 || 动态维护树上路径 || 涉及LCA点转序列 || 对欧拉环游序用数据结构维护:1192B

https://www.luogu.com.cn/problem/CF1192B

对于直径的求法,常用dp或两次dfs,但如果要动态维护似乎都不太方面,那么可以维护树上路径最大值。

树上路径为:

d e p u + d e p v − 2 × d e p l c a ( u , v ) dep_u+dep_v-2\times dep_{lca(u,v)} depu+depv2×deplca(u,v)

为方便求 l c a ( u , v ) lca(u,v) lca(u,v),可以直接化为树上欧拉环游序,任意 u , v u,v u,v 中必有 l c a ( u , v ) lca(u,v) lca(u,v) ,而且 l c a ( u , v ) lca(u,v) lca(u,v) 必然为任意 u , v u,v u,v 中最浅的点

在这里插入图片描述
然后直接拿个线段树维护即可

总结:

  1. 动态维护直径
  2. 动态维护树上路径
  3. 涉及LCA点转欧拉环游序
  4. 对欧拉环游序用数据结构维护

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/111700.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

图解算法--查找算法

目录 查找算法 一、顺序查找 二、二分法查找 三、插值查找法 四、斐波那契查找法 查找算法 查找算法根据数据量的大小,可以将其分为以下两种 内部查找:内部查找是指在内存或内部存储器中进行查找操作的算法。内部查找适用于数据量较小、存储在内存…

概念解析 | 量子机器学习:将量子力学与人工智能的奇妙融合

注1:本文系“概念解析”系列之一,致力于简洁清晰地解释、辨析复杂而专业的概念。本次辨析的概念是:量子机器学习。 量子机器学习:将量子力学与人工智能的奇妙融合 量子增强机器学习:量子经典混合卷积神经网络 量子机器学习是量子计算和机器学习的结合,它利用量子力学的特…

探讨uniapp的路由与页面栈及参数传递问题

1首先引入页面栈 框架以栈的形式管理当前所有页面, 当发生路由切换的时候,页面栈的表现如下: 页面的路由操作无非:初始化、打开新页面、页面重定向、页面返回、tab切换、重加载。 2页面路由 uni-app 有两种页面路由跳转方式&am…

【实训项目】精点考研

1.设计摘要 如果说高考是一次能够改变命运的考试,那么考研应该是另外一次。为什么那么多人都要考研呢?从中国教育在线官方公布是考研动机调查来看,大家扎堆考研的原因大概集中在这6个方面:本科就业压力大,提升竞争力、…

视频汇聚/视频云存储/视频监控管理平台EasyCVR视频平台添加萤火云设备的具体操作步骤

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快,可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等,以及支持厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…

解析肖特基二极管NRVBS360BNT3G整流器的优缺点及应用

何为肖特基二极管整流器? 是一种常用的电子器件,用于将交流信号转换为直流信号。它由一个PN结和一个金属接触组成,具有较低的正向压降和快速的开关特性。 在正向偏置下,肖特基二极管具有较低的正向压降,通常为0.3-0.…

笔记本电脑功率怎么看?记好这2个方法!

在使用笔记本电脑时,其功率是一个很重要的指标。笔记本电脑功率是影响其性能、续航和热管理的重要因素。不同的功率水平可以带来不同的使用体验。 本文将解释不同的笔记本电脑功率对设备的影响,并详细介绍几种查看笔记本电脑功率的方法。继续往下看吧&a…

安全生产作业现场违规行为识别 opencv

安全生产作业现场违规行为识别算法通过pythonopencv网络模型算法框架设定了各种合规行为和违规行为的模型,安全生产作业现场违规行为识别算法检测到违规行为,将立即进行抓拍并发送告警信息给相关人员,以便及时采取相应的处置措施。OpenCV是一…

基于OV2640/ OV5640 的图像采集显示系统

基于OV2640/ OV5640 的图像采集显示系统系列文章目录: (1)基于 OV5640 摄像头理论知识讲解-成像和采样原理 (2)基于 OV5640 摄像头理论知识讲解-数字接口和控制接口 (3)基于 OV5640 摄像头理论知…

vscode+ros开发环境搭建

目录 介绍 前提 vscode安装 vscode插件安装 工作空间准备 打开vscode 创建catkin包 编写cpp代码 编译 运行 启动ros服务 监听话题 启动ros测试 介绍 ros开发是机器人开发中必不可少的工作,语言选择可以是c,也可以是python。工具的话,不能像wi…

ceph中PGLog处理流程

ceph的PGLog是由PG来维护,记录了该PG的所有操作,其作用类似于数据库里的undo log。PGLog通常只保存近千条的操作记录(默认是3000条, 由osd_min_pg_log_entries指定),但是当PG处于降级状态时,就会保存更多的日志&#x…

React 生命周期

React的生命周期 一、什么是React的生命周期二、传统生命周期2.1、挂载(Mounting)2.2、更新(Updating)2.3、卸载(Unmounting)2.4、API2.4.1、render2.4.1.1、Updating 阶段,render调用完还有可能…

WPF基础入门-Class6-WPF通知更改

WPF基础入门 Class6-WPF通知 1、显示页面&#xff1a; <Grid><StackPanel><TextBox Text"{Binding Name}"></TextBox><TextBox Text"{Binding Title}"></TextBox><Button Command"{Binding ShowCommand}&qu…

初次跑yolo5遇到的一些问题

1. ImportError: cannot import name COMMON_SAFE_ASCII_CHARACTERS‘ from charset-normalizerconstant‘ 这个报错可能是由于charset_normalizer模块的版本问题引起的。尝试更新charset_normalizer模块到最新版本&#xff0c;或者使用较旧的版本&#xff0c;看看是否可以解…

用AI + Milvus Cloud搭建着装搭配推荐系统

在上一篇文章中,我们学习了如何利用人工智能技术(例如开源 AI 向量数据库 Milvus Cloud 和 Hugging Face 模型)寻找与自己穿搭风格相似的明星。在这篇文章中,我们将进一步介绍如何通过对上篇文章中的项目代码稍作修改,获得更详细和准确的结果,文末附赠彩蛋。 注:试用此…

Ansys Zemax | 手机镜头设计 - 第 2 部分:使用 OpticsBuilder 实现光机械封装

本文是3篇系列文章的一部分&#xff0c;该系列文章将讨论智能手机镜头模块设计的挑战&#xff0c;从概念、设计到制造和结构变形的分析。本文是三部分系列的第二部分。概括介绍了如何在 CAD 中编辑光学系统的光学元件以及如何在添加机械元件后使用 Zemax OpticsBuilder 分析系统…

Python切换输入法的实战代码

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

大模型开发05:PDF 翻译工具开发实战

大模型开发实战05:PDF 翻译工具开发实战 PDF-Translator 机器翻译是最广泛和基础的 NLP 任务 PDF-Translator PDF 翻译器是一个使用 AI 大模型技术将英文 PDF 书籍翻译成中文的工具。这个工具使用了大型语言模型 (LLMs),如 ChatGLM 和 OpenAI 的 GPT-3 以及 GPT-3.5 Turbo 来…

NewStarCTF 2022 web方向题解 wp

----------WEEK1---------- BUU NewStarCTF 公开赛赛道 WEEK1 [NotPHP] 先看题目&#xff0c;要传参加绕过。 分析一下代码&#xff1a;首先get一个datadata://test/plain,Wel…。然后key1和2用数组可以绕过。num2077a可以绕过弱类型。eval()中的php语句被#注释了&#xff0c…