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

acwing算法提高之图论--最近公共祖先

目录

  • 1 介绍
  • 2 训练

1 介绍

本博客用来记录"对于有根图中,求最近公共祖先"的题目。

求解方法:

  1. 向上标记法。每次求两个结点的最近公共祖先的时间复杂度是O(N)。由于时间复杂度较高,通常不用。
  2. 倍增法。

倍增法重要思路:预处理出两个数组fa[i][j]depth[i]。其中fa[i][j]表示从i开始,向上走2^j步所能走到的结点。0<=j<=logndepth[i]表示深度,为到根结点的距离再加上1。

哨兵:如果从i开始跳2^j步会跳过根结点,那么fa[i][j] = 0depth[0] = 0

倍增法重要步骤:

  1. 先将两个点跳到同一层。
  2. 让两个点同时往上跳,一直跳到它们的最近公共祖先的下一层。

倍增法的时间复杂度分析:预处理的时间复杂度为O(NlogN),查询的时间复杂度为O(logN)

2 训练

题目1:1172祖孙询问

C++代码如下,

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>using namespace std;const int N = 40010;
int n, m;
int depth[N], fa[N][16];
int ancestor;
unordered_map<int, vector<int>> g;void bfs(int root) {memset(depth, 0x3f, sizeof depth);depth[0] = 0;depth[root] = 1; queue<int> q;q.push(root);while (!q.empty()) {int a = q.front();q.pop();for (auto b : g[a]) {if (depth[b] > depth[a] + 1) {depth[b] = depth[a] + 1;q.push(b);fa[b][0] = a;for (int k = 1; k <= 15; ++k) {fa[b][k] = fa[fa[b][k-1]][k-1];}}}}return;
}int lca(int a, int b) {//倍增法if (depth[a] < depth[b]) swap(a, b);for (int k = 15; k >= 0; --k) {if (depth[fa[a][k]] >= depth[b]) {a = fa[a][k];}}if (a == b) return a;for (int k = 15; k >= 0; --k) {if (fa[a][k] != fa[b][k]) {a = fa[a][k];b = fa[b][k];}}return fa[a][0];
}int main() {cin >> n;int a, b;for (int i = 0; i < n; ++i) {cin >> a >> b;if (b == -1) {ancestor = a;} else {g[a].emplace_back(b);g[b].emplace_back(a);        }}cin >> m;vector<pair<int,int>> queries;for (int i = 0; i < m; ++i) {cin >> a >> b;queries.emplace_back(a,b);}//从根结点开始遍历bfs(ancestor);for (auto [a, b] : queries) {int x = lca(a, b);if (a == x) {puts("1");} else if (b == x) {puts("2");} else {puts("0");}}return 0;
}

题目2:1171距离

C++代码如下,


相关文章:

acwing算法提高之图论--最近公共祖先

目录 1 介绍2 训练 1 介绍 本博客用来记录"对于有根图中&#xff0c;求最近公共祖先"的题目。 求解方法&#xff1a; 向上标记法。每次求两个结点的最近公共祖先的时间复杂度是O(N)。由于时间复杂度较高&#xff0c;通常不用。倍增法。 倍增法重要思路&#xff1…...

C语言 函数——断言与防御式编程

目录 如何确定假设的真假&#xff1f; 断言 防御式编程&#xff08;Defensive programming&#xff09; 如何确定假设的真假&#xff1f; 程序中的假设 *某个特定点的某个表达式的值一定为真 *某个特定点的某个表达式的值一定位于某个区间等 问题&#xff1a;如何确定这些…...

【opencv】示例-travelsalesman.cpp 使用模拟退火算法求解旅行商问题

// 载入 OpenCV 的核心头文件 #include <opencv2/core.hpp> // 载入 OpenCV 的图像处理头文件 #include <opencv2/imgproc.hpp> // 载入 OpenCV 的高层GUI(图形用户界面)头文件 #include <opencv2/highgui.hpp> // 载入 OpenCV 的机器学习模块头文件 #includ…...

【linux深入剖析】深入理解软硬链接 | 动静态库的制作以及使用

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 1.理解软硬链接1.1 操作观…...

xss常用标签和触发事件

无过滤情况 <script> <scirpt>alert("xss");</script> <img> 图片加载错误时触发 <img src"x" οnerrοralert(1)> <img src"1" οnerrοreval("alert(xss)")> 鼠标指针移动到元素时触发 <im…...

WPF中Binding的原理和应用

WPF中Binding的原理和应用 在WPF中&#xff0c;Binding机制是实现数据与界面的连接和同步的重要工具。了解Binding的原理和应用&#xff0c;对于开发人员来说是非常重要的。本文将详细介绍WPF中Binding的原理和应用&#xff0c;帮助读者更好地理解和运用这一强大的机制。 Bin…...

探索设计模式的魅力:深度挖掘响应式模式的潜力,从而精准优化AI与机器学习项目的运行效能,引领技术革新潮流

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 挖掘响应式模式&#xff0c;优化AI与机器学习项目性能&#xff0c;引领技术新潮流 ✨机器学习界的…...

《经典论文阅读2》基于随机游走的节点表示学习—Deepwalk算法

word2vec使用语言天生具备序列这一特性训练得到词语的向量表示。而在图结构上&#xff0c;则存在无法序列的难题&#xff0c;因为图结构它不具备序列特性&#xff0c;就无法得到图节点的表示。deepwalk 的作者提出&#xff1a;可以使用在图上随机游走的方式得到一串序列&#x…...

Java实现二叉树(下)

1.前言 http://t.csdnimg.cn/lO4S7 在前文我们已经简单的讲解了二叉树的基本概念&#xff0c;本文将讲解具体的实现 2.基本功能的实现 2.1获取树中节点个数 public int size(TreeNode root){if(rootnull){return 0;}int retsize(root.left)size(root.right)1;return ret;}p…...

Hello 算法10:搜索

https://www.hello-algo.com/chapter_searching/binary_search/ 二分查找法 给定一个长度为 n的数组 nums &#xff0c;元素按从小到大的顺序排列&#xff0c;数组不包含重复元素。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素&#xff0c;则返回 -1 。 # 首…...

常见分类算法详解

在机器学习和数据科学的广阔领域中&#xff0c;分类算法是至关重要的一环。它广泛应用于各种场景&#xff0c;如垃圾邮件检测、图像识别、情感分析等。本文将深入剖析几种常见的分类算法&#xff0c;帮助读者理解其原理、优缺点以及应用场景。 一、K近邻算法&#xff08;K-Nea…...

推送恶意软件的恶意 PowerShell 脚本看起来是人工智能编写的

威胁行为者正在使用 PowerShell 脚本&#xff0c;该脚本可能是在 OpenAI 的 ChatGPT、Google 的 Gemini 或 Microsoft 的 CoPilot 等人工智能系统的帮助下创建的。 攻击者在 3 月份的一次电子邮件活动中使用了该脚本&#xff0c;该活动针对德国的数十个组织来传播 Rhadamanthy…...

微服务之Consul 注册中心介绍以及搭建

一、微服务概述 1.1单体架构 单体架构&#xff08;monolithic structure&#xff09;&#xff1a;顾名思义&#xff0c;整个项目中所有功能模块都在一个工程中开发&#xff1b;项目部署时需要对所有模块一起编译、打包&#xff1b;项目的架构设计、开发模式都非常简单。 当项…...

MES生产管理系统:私有云、公有云与本地化部署的比较分析

随着信息技术的迅猛发展&#xff0c;云计算作为一种新兴的技术服务模式&#xff0c;已经深入渗透到企业的日常运营中。在众多部署方式中&#xff0c;私有云、公有云和本地化部署是三种最为常见的选择。它们各自具有独特的特点和适用场景&#xff0c;并在不同程度上影响着企业的…...

【core analyzer】core analyzer的介绍和安装详情

目录 &#x1f31e;1. core和core analyzer的基本概念 &#x1f33c;1.1 coredump文件 &#x1f33c;1.2 core analyzer &#x1f31e;2. core analyzer的安装详细过程 &#x1f33c;2.1 方式一 简单但不推荐 &#x1f33c;2.2 方式二 推荐 &#x1f33b;2.2.1 安装遇到…...

个人练习之-jenkins

虚拟机环境搭建(买不起服务器 like me) 重点: 0 虚拟机防火墙关闭 systemctl stop firewalld.service systemctl disable firewalld.service 1 (centos7.6)网络配置 (vmware 编辑 -> 虚拟网络编辑器 -> 选择NAT模式 ->NAT设置查看网关) vim /etc/sysconfig/network-sc…...

初探vercel托管项目

文章目录 第一步、注册与登录第二步、本地部署 在个人网站部署的助手vercel&#xff0c;支持 Github部署&#xff0c;只需简单操作&#xff0c;即可发布&#xff0c;方便快捷&#xff01; 第一步、注册与登录 进入vercel【官网】&#xff0c;在右上角 login on&#xff0c;可登…...

软考 - 系统架构设计师 - 质量属性例题 (2)

问题1&#xff1a; 、 问题 2&#xff1a; 系统架构风险&#xff1a;指架构设计中 &#xff0c;潜在的&#xff0c;存在问题的架构决策所带来的隐患。 敏感点&#xff1a;指为了实现某个质量属性&#xff0c;一个或多个构件所具有的特性 权衡点&#xff1a;指影响多个质量属性…...

基于Python豆瓣电影数据可视化分析系统的设计与实现

大数据可视化项目——基于Python豆瓣电影数据可视化分析系统的设计与实现 2024最新项目 项目介绍 本项目旨在通过对豆瓣电影数据进行综合分析与可视化展示&#xff0c;构建一个基于Python的大数据可视化系统。通过数据爬取收集、清洗、分析豆瓣电影数据&#xff0c;我们提供了…...

【已开源】​基于stm32f103的爬墙小车

​基于stm32f103的遥控器无线控制爬墙小车&#xff0c;实现功能为可平衡在竖直墙面上&#xff0c;并进行移动和转向&#xff0c;具有超声波防撞功能。 直接上&#xff1a; 演示视频如&#xff1a;哔哩哔哩】 https://b23.tv/BzVTymO 项目说明&#xff1a; 在这个项目中&…...

PCL 基于马氏距离KMeans点云聚类

文章目录 一、简介二、算法步骤三、代码实现四、实现效果参考资料一、简介 在诸多的聚类方法中,K-Means聚类方法是属于“基于原型的聚类”(也称为原型聚类)的方法,此类方法均是假设聚类结构能通过一组原型刻画,在现实聚类中极为常用。通常情况下,该类算法会先对原型进行初始…...

libVLC 视频窗口上叠加透明窗口

很多时候&#xff0c;我们需要在界面上画一些三角形、文字等之类的东西&#xff0c;我们之需要重写paintEvent方法&#xff0c;比如像这样 void Widget::paintEvent(QPaintEvent *event) 以下就是重写的代码。 void Widget::paintEvent(QPaintEvent *event) {//创建QPainte…...

MySQL基础入门上篇

MySQL基础 介绍 mysql -uroot -p -h127.0.0.1 -P3306项目设计 具备数据库一定的设计能力和操作数据的能力。 数据库设计DDL 定义 操作 显示所有数据库 show databases;创建数据库 create database db02;数据库名唯一&#xff0c;不能重复。 查询是否创建成功 加入一些…...

Docker搭建FFmpeg

FFmpeg 是一套可以用来记录、转换数字音频、视频&#xff0c;并能将其转化为流的完整解决方案。FFmpeg 包含了领先的音视频编解码库libavcodec&#xff0c;可以用于各种视频格式的转换。 应用场景包括&#xff1a; 视频转换&#xff1a;把视频从一种格式转换成另一种格式。视…...

Hudi-ubuntu环境搭建

hudi-ubuntu环境搭建 运行 1.编译Hudi #1.把maven安装包上传到服务器 # 官网下载安装包 https://archive.apache.org/dist/maven/maven-3/ scp -r D:\Users\zh\Desktop\Hudi\compressedPackage\apache-maven-3.6.3-bin.tar.gz zhangheng10.8.4.212:/home/zhangheng/hudi/com…...

Hive进阶Day05

一、HDFS分布式文件存储系统 1-1 HDFS的存储机制 按块&#xff08;block&#xff09;存储 hdfs在对文件数据进行存储时&#xff0c;默认是按照128M(包含)大小进行文件数据拆分&#xff0c;将不同拆分的块数据存储在不同datanode服务器上 拆分后的块数据会被分别存储在不同的服…...

ssh爆破服务器的ip-疑似肉鸡

最近发现自己的ssh一直有一些人企图使用ssh暴力破解的方式进行密码破解.就查看了一下,真是网络安全太可怕了. 大家自己的服务器密码还是要设置好,管好,做好最基本的安全措施,不然最后只能沦为肉鸡. ssh登陆日志可以在/var/log下看到,ubuntu的话为auth.log,centos为secure文件 查…...

4.JVM八股

JVM空间划分 线程共享和线程私有 1.7&#xff1a; 线程共享&#xff1a; 堆、方法区 线程私有&#xff1a; 虚拟机栈、本地方法栈、程序计数器 本地内存 1.8&#xff1a; 线程共享&#xff1a; 堆 线程私有&#xff1a; 老三样 本地内存&#xff0c;元空间 程序计数器 …...

内网渗透系列-mimikatz的使用以及后门植入

内网渗透系列-mimikatz的使用以及后门植入 文章目录 内网渗透系列-mimikatz的使用以及后门植入前言mimikatz的使用后门植入 msf永久后门植入 &#xff08;1&#xff09;Meterpreter后门&#xff1a;Metsvc&#xff08;2&#xff09;Meterpreter后门&#xff1a;Persistence NC后…...

5G网络开通与调测ipv4

要求如下&#xff1a; 1. 勘站规划 1. 【重】首先观察NR频点&#xff0c;完成设备选型 2645--选择N41 3455--选择N78 4725--选择N79 设备选型如下&#xff1a;观察AAU的通道数&#xff0c;最大发射功率&#xff1b;选择N41的选型频段也要选41 2. …...

丹徒网站建设价格/个人怎么做免费百度推广

重构&#xff1a;改变既有代码的一剂良药 1. 什么是系统重构&#xff1f; 它是一套严谨而安全的过程方法&#xff0c;它通过一系列行之有效的方法与措施&#xff0c;保证软件在优化的同时&#xff0c;不会引入新的bug,保证软件改造的质量。 2. 系统重构的概念 系统重构&#xf…...

网易邮箱网页版/上海外包seo

这里只写cacti监控lvs的部分&#xff0c;前提是cacti安装完成。服务端&#xff08;下载2个附件&#xff09;1.服务端添加模板cacti_data_query_snmp_lvs.xml2.将 snmp-lvs.xml 拷贝到source 目录下客户端(lvs机器-这里针对5和4的32位系统&#xff0c;el5_64位不适用)A 安装 net…...

网站模板用什么做/品牌推广方案包括哪些

前言 流式计算对稳定性敏感&#xff0c;所以我们在编写作业时一定会做好防御性编程&#xff0c;如各种判空、边界条件、安全的类型转换、格式判断、异常捕获等。但是墨菲定律说得好&#xff1a; Anything that can go wrong will go wrong. 换言之&#xff0c;我们写再多的防御…...

汉南网站建设/最新中国新闻

class Solution { public:vector<int> decode(vector<int>& encoded, int first) {int n encoded.size();vector<int> res(n 1);res[0] first;for(int i 1; i < n; i) {res[i] encoded[i - 1] ^ res[i - 1];}return res;} };...

企业网站建设建议/百度正式员工工资待遇

第一章 完善用户相关信息 用户注册与登录 数据库表设计&#xff1a;用户表、用户信息表相关接口&#xff08;API&#xff09;&#xff1a;获取RSA公钥、用户注册、用户登录 数据库表设计及相关实体类设计 用户表 用户信息表 根据这两张数据库表创建对应的实体类 基于JWT的用…...

有没有在线做动图的网站/seo职业培训班

大家好&#xff0c;今天分享一篇来自装机吧官网(zhuangjiba.com)的图文教程。相信大家日常在使用电脑的时候&#xff0c;都遇到过系统删除文件需要管理员权限的问题。那么&#xff0c;系统删除文件需要管理员权限的问题时该怎么办呢&#xff1f;接下来&#xff0c;小编就以win1…...