LCA
定义
最近公共祖先简称 LCA(Lowest Common Ancestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。
性质
- 如果
不为
的祖先并且
不为
的祖先,那么
分别处于
的两棵不同子树中; - 前序遍历中,
出现在所有
中元素之前,后序遍历中
则出现在所有
中元素之后; - 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先,即
; - 两点的最近公共祖先必定处在树上两点间的最短路
倍增算法
过程
倍增算法是最经典的 LCA 求法,他是朴素算法的改进算法。通过预处理
数组,游标可以快速移动,大幅减少了游标跳转次数。
表示点
的第
个祖先。
数组可以通过 dfs 预处理出来。
现在我们看看如何优化这些跳转: 在调整游标的第一阶段中,我们要将
两点跳转到同一深度。我们可以计算出
两点的深度之差,设其为
。通过将
进行二进制拆分,我们将
次游标跳转优化为「
的二进制表示所含 1 的个数」次游标跳转。 在第二阶段中,我们从最大的
开始循环尝试,一直尝试到
(包括
),如果
,则
,那么最后的 LCA 为
。
性质
倍增算法的预处理时间复杂度为
,单次查询时间复杂度为
。 另外倍增算法可以通过交换 fa 数组的两维使较小维放在前面。这样可以减少 cache miss 次数,提高程序效率。
例题
可先求出 LCA,再结合性质
进行解答。也可以直接在求 LCA 时求出结果。
参考代码
|
相关文章:
LCA
定义 最近公共祖先简称 LCA(Lowest Common Ancestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。 性质 如果 不为 的祖先并且 不为 的祖先,那么 分别处于 的两棵不同子树中&#…...
ts学习02-数据类型
新建index.html <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title> </h…...
javaSE的发展历史以及openjdk和oracleJdk
1 JavaSE 的发展历史 1.1 Java 语言的介绍 SUN 公司在 1991 年成立了一个称为绿色计划(Green Project)的项目,由 James Gosling(高斯林)博士领导,绿色计划的目的是开发一种能够在各种消费性电子产品&…...
【入门Flink】- 10基于时间的双流联合(join)
统计固定时间内两条流数据的匹配情况,需要自定义来实现——可以用窗口(window)来表示。为了更方便地实现基于时间的合流操作,Flink 的 DataStrema API 提供了内置的 join 算子。 窗口联结(Window Join) 一…...
【Python Opencv】图片与视频的操作
文章目录 前言一、opencv图片1.1 读取图像1.2 显示图像1.3 写入图像1.4 示例代码 二、Opencv视频2.1 从相机捕获视频获取摄像头一帧一帧读取显示图片VideoCapture 中的get和set函数示例代码 2.2 从文件播放视频示例代码 2.3 保存视频示例代码 总结 前言 在计算机视觉和图像处理…...
【从入门到起飞】JavaAPI—System,Runtime,Object,Objects类
🎊专栏【JavaSE】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【如愿】 🎄欢迎并且感谢大家指出小吉的问题🥰 文章目录 🍔System类⭐exit()⭐currentTimeMillis()🎄用…...
【Git】的分支和标签的讲解及实际应用场景
目录 讲解 环境讲述 分支标签的区别 分支 命令 场景应用 标签 命令 标签规范 讲解 环境讲述 当软件从开发到正式环境部署的过程中,不同环境的作用 开发环境:用于开发人员进行软件开发、测试和调试。在这个环境中,开发人员可以快速地…...
修改django开发环境runserver命令默认的端口
runserver默认8000端口 虽然python manage.py runserver 8080 可以指定端口,但不想每次runserver都添加8080这个参数 可以通过修改manage.py进行修改,只需要加三行: from django.core.management.commands.runserver import Command as Ru…...
kubeadm安装k8s高可用集群
目录 一、环境规划 二、注意事项: 三、环境准备: 1. 关闭防火墙规则,关闭selinux,关闭swap交换: 2. 修改主机名 3. 所有节点修改hosts文件: 4. 所有节点时间同步: 5. 所有节点实现Linux的资…...
来看看电脑上有哪些不为人知的小众软件?
电脑上的各类软件有很多,除了那些常见的大众化软件,还有很多不为人知的小众软件,专注于实用功能,简洁干净、功能强悍。 1.桌面停靠栏工具——BitDock BitDock是一款运行在Windows系统中的桌面停靠栏工具,功能实…...
一个进程最多可以创建多少个线程?
前言 话不多说,先来张脑图~ linux 虚拟内存知识回顾 虚拟内存空间长啥样 在 Linux 操作系统中,虚拟地址空间的内部又被分为内核空间和用户空间两部分,不同位数的系统,地址空间的范围也不同。比如最常见的 32 位和 64 位系统&am…...
ElasticSearch文档分析
ElasticSearch文档分析 包含下面的过程: 将一块文本分成适合于倒排索引的独立的 词条将这些词条统一化为标准格式以提高它们的“可搜索性”,或者 recall 分析器执行上面的工作。分析器实际上是将三个功能封装到了一个包里: 字符过滤器 首先&a…...
Xilinx FPGA平台DDR3设计详解(一):DDR SDRAM系统框架
DDR SDRAM(双倍速率同步动态随机存储器)是一种内存技术,它可以在时钟信号的上升沿和下降沿都传输数据,从而提高数据传输的速率。DDR SDRAM已经发展了多代,包括DDR、DDR2、DDR3、DDR4和DDR5,每一代都有不同的…...
Spring Data JPA方法名命名规则
最近巩固一下JPA,网上看到这些资料,这里记录巩固一下。 一、Spring Data Jpa方法定义的规则 简单条件查询 简单条件查询:查询某一个实体类或者集合。 按照Spring Data的规范的规定,查询方法以find | read | get开头&…...
【Leetcode Sheet】Weekly Practice 15
Leetcode Test 2586 统计范围内的元音字符串数(11.7) 给你一个下标从 0 开始的字符串数组 words 和两个整数:left 和 right 。 如果字符串以元音字母开头并以元音字母结尾,那么该字符串就是一个 元音字符串 ,其中元音字母是 a、e、i、o、u…...
人力资源社会保障部办公厅关于推行专业技术人员职业资格电子证书的通知
(人社厅发〔2021〕97号) 各省、自治区、直辖市及新疆生产建设兵团人力资源社会保障厅(局),中共海南省委人才发展局,国务院有关部门、直属机构人事部门,有关协会、学会: 为贯彻落实…...
什么是光电耦合器?如何选择型号及种类
光电耦合器(英文缩写为OC)亦称光电隔离器,简称光耦;以光为媒介传输电信号;它对输入、输出电信号有良好的隔离作用,是目前种类最多、用途最广的光电器件之一;所以,它在各种电路中得到广泛的应用。 光耦合器…...
hive里因为列名用了关键字导致建表失败
代码 现象 ParseException line 6:4 cannot recognize input near percent String COMMENT in column name or primary key or foreign key 23/11/13 11:52:57 ERROR org.apache.hadoop.hive.ql.Driver: FAILED: ParseException line 6:4 cannot recognize input near percent …...
MySQL 报错 incorrect datetime value ‘0000-00-00 00:00:00‘ for column
使用navicat导入数据时报错: MySQL 报错 incorrect datetime value ‘0000-00-00 00:00:00’ for column 这是因为当前的MySQL不支持datetime为0的情况。 MySQL报incorrect datetime value ‘0000-00-00 00:00:00’ for column错误原因,是由于在MySQL5.7…...
Jira Data Center(非集群)升级操作
一、升级准备 Jira 管理界面执行升级检查下载升级包,使用原操作方式相同的方式安装。我这里原来的版本是通过./atlassian-jira-software-9.11.2-x64.bin安装的,接下来下载atlassian-jira-software-9.11.3-x64.bin的安装文件停止 Jira,bin/st…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
算术操作符与类型转换:从基础到精通
目录 前言:从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符:、-、*、/、% 赋值操作符:和复合赋值 单⽬操作符:、--、、- 前言:从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...
客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践
01技术背景与业务挑战 某短视频点播企业深耕国内用户市场,但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大,传统架构已较难满足当前企业发展的需求,企业面临着三重挑战: ① 业务:国内用户访问海外服…...
Linux系统:进程间通信-匿名与命名管道
本节重点 匿名管道的概念与原理匿名管道的创建命名管道的概念与原理命名管道的创建两者的差异与联系命名管道实现EchoServer 一、管道 管道(Pipe)是一种进程间通信(IPC, Inter-Process Communication)机制,用于在不…...
大陆4D毫米波雷达ARS548调试
本文介绍了大陆ARS548毫米波雷达的调试与测试流程,主要包括以下内容: 设备参数:最大检测距离301m(可调93-1514m),支持gPTP时间同步。 接线调试: Windows需使用USB-RJ45转换器 Linux可直接连接网…...
