树链剖分相关
树链剖分这玩意儿还挺重要的,是解决静态树问题的一个很好的工具~
这里主要介绍一下做题时经常遇到的两个操作:
1.在线求LCA
int LCA(int x,int y){while(top[x]!=top[y])if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];else y=fa[top[y]];return dep[x]<dep[y]?x:y;
}
这个非常重要!!!
在很多题目中,我们需要借助LCA 来解题
2.换根操作
换一个根就重新剖一次当然是不现实的
不妨就先以1号节点为根剖一下
树链修改值当然直接按照重链在线段树上改就好了
主要就是讨论以x为根的子树对于不同的根时的dfn序范围
那么设当前的根是root
①:x==root:范围当然就是全局
②:x不在1到root的链上,在其他的支叉上:root为根或是1为根没有影响,
按普通套路来,即范围是[dfn[x],dfn[x]+size[x]-1]
图中蓝色的标号就是根据轻重链剖分进行的树上节点再标号id,红色笔迹标出的每一条树链就是一条重链,可以根据这个图来感性理解一下x不在1到root链上时的范围为什么不变
③:x在1到root的链上:这就是要处理的重点了
上图中紫色圈出的节点即是当前root,绿色圈出的节点即是要查询的子树的根x,那么可以看出当前x在1到root的链上。思考现在x的子树,其实就是除去x往root方向的那个子树外,所有的节点
int query_son(int x){if(root==x) return st[1];if(LCA(x,root)==x){int ans=2147483647,from;for(int i=head[x];i!=-1;i=edge[i].nxt)if(LCA(edge[i].v,root)==edge[i].v){from=edge[i].v;break;}if(tid[from]>1) ans=min(ans,query(1,1,n,1,tid[from]-1));if(tid[from]+size[from]<=n) ans=min(ans,query(1,1,n,tid[from]+size[from],n));return ans;}return query(1,1,n,tid[x],tid[x]+size[x]-1);
}
相关文章:

树链剖分相关
树链剖分这玩意儿还挺重要的,是解决静态树问题的一个很好的工具~ 这里主要介绍一下做题时经常遇到的两个操作: 1.在线求LCA int LCA(int x,int y){while(top[x]!top[y])if(dep[top[x]]>dep[top[y]]) xfa[top[x]];else yfa[top[y]];return dep[x]&l…...

如何将Grammarly内嵌到word中(超简单!)
1、下载 安装包下载链接见文章结尾 官网的grammarly好像只能作为单独软件使用,无法内嵌到word中🧐🧐🧐 2、双击安装包(安装之前把Office文件都关掉) 3、安装完成,在桌面新建个word文件并打开 注…...

OTG -- 用于FPGA的ULPI接口芯片USB3320讲解(续)
目录 1 背景 2 USB3320在FPGA上的应用 1 背景 最近使用FPGA驱动USB PHY实现高速USB功能,为了方便,购买了一块微雪的USB3300子板,发现怎么都枚举不了,使用逻辑分析仪抓取波形,和STM32F407USB3300波形进行对比…...

了解劳动准备差距:人力资源专业人员的战略
劳动准备差距是一个紧迫的问题,在全球人事部门回应,谈论未开发的潜力和错过的机会。想象一下,人才和需求之间的悬崖之间有一座桥,这促使雇主思考:我们是否为员工提供了足够的设备来应对未来的考验? 这种不…...

SAP PS学习笔记02 - 网络,活动,PS文本,PS文书(凭证),里程碑
上一章讲了PS 的概要,以及创建Project,创建WBS。 SAP PS学习笔记01 - PS概述,创建Project和WBS-CSDN博客 本章继续讲PS的后续内容。包括下面的概念和基本操作,以及一些Customize: - 网络(Network…...

Github 2024-07-07php开源项目日报 Top9
根据Github Trendings的统计,今日(2024-07-07统计)共有9个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量PHP项目9Blade项目2JavaScript项目1Laravel:表达力和优雅的 Web 应用程序框架 创建周期:4631 天开发语言:PHP, BladeStar数量:75969 个Fork数…...
算法训练(leetcode)第二十六天 | 452. 用最少数量的箭引爆气球、435. 无重叠区间、763. 划分字母区间
刷题记录 452. 用最少数量的箭引爆气球思路一思路二 435. 无重叠区间763. 划分字母区间 452. 用最少数量的箭引爆气球 leetcode题目地址 思路一 先按起始坐标从小到大排序。排序后找交集并将交集存入一个数组中,遍历气球数组从交集数组中找交集,找到与…...
Ubuntu 下 Docker安装 2024
Ubuntu 下 Docker安装 2024 安装1.卸载老版本2.更新apt包索引3.安装必要工具包4.添加Docker GPG秘钥5.配置仓库源6.安装Docker Engine7.启动docker 国内镜像源下架的解决办法1.修改文件 /etc/docker/daemon.json2.换源3.查看是否换源成功4.重启 安装 1.卸载老版本 sudo apt-ge…...

发送者的可靠性
这篇文章是了解MQ消息的可靠性,即:消息应该至少被消费者处理1次 那么问题来了: 我们该如何确保MQ消息的可靠性?如果真的发送失败,有没有其它的兜底方案? 首先,我们一起分析一下消息丢失的可能…...

Profibus_DP转ModbusTCP网关模块连马保与上位机通讯
Profibus转ModbusTCP网关模块(XD-ETHPB20)广泛应用于工业自动化领域。例如,可以将Profibus网络中的传感器数据转换为ModbusTCP协议,实现数据的实时监控和远程控制。本文介绍了如何利用Profibus转ModbusTCP网关(XD-ETHP…...

移动应用:商城购物类,是最常见的,想出彩或许就差灵犀一指
在移动应用中,商城购物类的非常常见,模式也非常成熟,想要设计的出彩也是有难度的,这次分享一些不同的。...
linux 查看历史命令列表来访问之前的内容的命令是:history
在Linux中,要查看历史命令列表以访问之前的内容,你可以使用history命令。这个命令会显示你当前shell会话(或者,如果你指定了参数,可能是所有会话)中执行过的命令列表。 基本用法 简单地输入history并按下…...

NAS免费用,鲁大师 AiNAS正式发布,「专业版」年卡仅需264元
7月10日,鲁大师召开新品发布会,正式发布旗下以“提供本地Ai部署和使用能力以及在线NAS功能”并行的复合软件产品:鲁大师 AiNAS。 全新的鲁大师 AiNAS将持续满足现如今大众对于数字化生活的全新需求,将“云存储”的便捷与NAS的大容…...
spring监听事件
1、spring-监听事件基本原理 Spring的事件监听机制和发布订阅机制是很相似的:发布了一个事件后,监听该类型事件的所有监听器会触发相应的处理逻辑 2、Spring 监听事件相关规范 在Spring中,事件监听机制主要涉及到了一下几个关键的规范&#x…...

微软发布E2 TTS: 一种简单但效果优秀的文本转语音技术
本文介绍了一种名为“Embarrassingly Easy Text-to-Speech(E2 TTS)”的文本转语音系统。 该系统通过将输入文本转换为填充标记字符序列,并基于音频填充值任务训练流匹配基mel频谱生成器,实现了人类水平的自然度和最先进的说话人相…...

python爬虫加入进度条
安装tqdm和requests库 pip install tqdm -i https://pypi.tuna.tsinghua.edu.cn/simplepip install requests -i https://pypi.tuna.tsinghua.edu.cn/simple带进度条下载 import time # 引入time模块,用于处理时间相关的功能 from tqdm import * # 从tqdm包中…...
力扣844.比较含退格的字符串
力扣844.比较含退格的字符串 栈模拟 class Solution {public:bool backspaceCompare(string s, string t) {int n s.size(),m t.size();stack<char> s1,s2;for(int i0;i<n;i){s1.push(s[i]);if(s[i] #){if(s1.size() 1) s1.pop();else s1.pop(),s1.pop();}}for(i…...
用户特征和embedding层做Concatenation
要将用户特征与嵌入层进行连接,可以使用深度学习框架(如TensorFlow或PyTorch)中的基本操作。以下是使用PyTorch的示例代码,展示了如何将用户特征与嵌入层连接起来。 示例代码(使用PyTorch) 安装 PyTorch 如…...

Ubuntu20.04下修改samba用户密码
Ubuntu20.04下修改samba用户密码 在Ubuntu系统中,修改samba密码通常涉及到两个方面:更改samba用户的密码和重置samba服务的密码数据库。以下是如何进行操作的步骤: 1、更改samba用户密码: 打开终端,使用以下命令更改…...

PHP老照片修复文字识别图像去雾一键抠图微信小程序源码
🔍解锁复古魅力,微信小程序黑科技大揭秘!老照片修复&更多神奇功能等你来试! 📸 【老照片修复,时光倒流的美颜术】 你是否珍藏着一堆泛黄的老照片,却因岁月侵蚀而模糊不清?现在…...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...

Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...