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

树链剖分相关

树链剖分这玩意儿还挺重要的,是解决静态树问题的一个很好的工具~

这里主要介绍一下做题时经常遇到的两个操作:

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);
}

相关文章:

树链剖分相关

树链剖分这玩意儿还挺重要的&#xff0c;是解决静态树问题的一个很好的工具~ 这里主要介绍一下做题时经常遇到的两个操作&#xff1a; 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好像只能作为单独软件使用&#xff0c;无法内嵌到word中&#x1f9d0;&#x1f9d0;&#x1f9d0; 2、双击安装包&#xff08;安装之前把Office文件都关掉&#xff09; 3、安装完成&#xff0c;在桌面新建个word文件并打开 注…...

OTG -- 用于FPGA的ULPI接口芯片USB3320讲解(续)

目录 1 背景 2 USB3320在FPGA上的应用 1 背景 最近使用FPGA驱动USB PHY实现高速USB功能&#xff0c;为了方便&#xff0c;购买了一块微雪的USB3300子板&#xff0c;发现怎么都枚举不了&#xff0c;使用逻辑分析仪抓取波形&#xff0c;和STM32F407USB3300波形进行对比&#xf…...

了解劳动准备差距:人力资源专业人员的战略

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

SAP PS学习笔记02 - 网络,活动,PS文本,PS文书(凭证),里程碑

上一章讲了PS 的概要&#xff0c;以及创建Project&#xff0c;创建WBS。 SAP PS学习笔记01 - PS概述&#xff0c;创建Project和WBS-CSDN博客 本章继续讲PS的后续内容。包括下面的概念和基本操作&#xff0c;以及一些Customize&#xff1a; - 网络&#xff08;Network&#xf…...

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题目地址 思路一 先按起始坐标从小到大排序。排序后找交集并将交集存入一个数组中&#xff0c;遍历气球数组从交集数组中找交集&#xff0c;找到与…...

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消息的可靠性&#xff0c;即&#xff1a;消息应该至少被消费者处理1次 那么问题来了&#xff1a; 我们该如何确保MQ消息的可靠性&#xff1f;如果真的发送失败&#xff0c;有没有其它的兜底方案&#xff1f; 首先&#xff0c;我们一起分析一下消息丢失的可能…...

Profibus_DP转ModbusTCP网关模块连马保与上位机通讯

Profibus转ModbusTCP网关模块&#xff08;XD-ETHPB20&#xff09;广泛应用于工业自动化领域。例如&#xff0c;可以将Profibus网络中的传感器数据转换为ModbusTCP协议&#xff0c;实现数据的实时监控和远程控制。本文介绍了如何利用Profibus转ModbusTCP网关&#xff08;XD-ETHP…...

移动应用:商城购物类,是最常见的,想出彩或许就差灵犀一指

在移动应用中&#xff0c;商城购物类的非常常见&#xff0c;模式也非常成熟&#xff0c;想要设计的出彩也是有难度的&#xff0c;这次分享一些不同的。...

linux 查看历史命令列表来访问之前的内容的命令是:history

在Linux中&#xff0c;要查看历史命令列表以访问之前的内容&#xff0c;你可以使用history命令。这个命令会显示你当前shell会话&#xff08;或者&#xff0c;如果你指定了参数&#xff0c;可能是所有会话&#xff09;中执行过的命令列表。 基本用法 简单地输入history并按下…...

NAS免费用,鲁大师 AiNAS正式发布,「专业版」年卡仅需264元

7月10日&#xff0c;鲁大师召开新品发布会&#xff0c;正式发布旗下以“提供本地Ai部署和使用能力以及在线NAS功能”并行的复合软件产品&#xff1a;鲁大师 AiNAS。 全新的鲁大师 AiNAS将持续满足现如今大众对于数字化生活的全新需求&#xff0c;将“云存储”的便捷与NAS的大容…...

spring监听事件

1、spring-监听事件基本原理 Spring的事件监听机制和发布订阅机制是很相似的&#xff1a;发布了一个事件后&#xff0c;监听该类型事件的所有监听器会触发相应的处理逻辑 2、Spring 监听事件相关规范 在Spring中&#xff0c;事件监听机制主要涉及到了一下几个关键的规范&#x…...

微软发布E2 TTS: 一种简单但效果优秀的文本转语音技术

本文介绍了一种名为“Embarrassingly Easy Text-to-Speech&#xff08;E2 TTS&#xff09;”的文本转语音系统。 该系统通过将输入文本转换为填充标记字符序列&#xff0c;并基于音频填充值任务训练流匹配基mel频谱生成器&#xff0c;实现了人类水平的自然度和最先进的说话人相…...

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模块&#xff0c;用于处理时间相关的功能 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

要将用户特征与嵌入层进行连接&#xff0c;可以使用深度学习框架&#xff08;如TensorFlow或PyTorch&#xff09;中的基本操作。以下是使用PyTorch的示例代码&#xff0c;展示了如何将用户特征与嵌入层连接起来。 示例代码&#xff08;使用PyTorch&#xff09; 安装 PyTorch 如…...

Ubuntu20.04下修改samba用户密码

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

PHP老照片修复文字识别图像去雾一键抠图微信小程序源码

&#x1f50d;解锁复古魅力&#xff0c;微信小程序黑科技大揭秘&#xff01;老照片修复&更多神奇功能等你来试&#xff01; &#x1f4f8; 【老照片修复&#xff0c;时光倒流的美颜术】 你是否珍藏着一堆泛黄的老照片&#xff0c;却因岁月侵蚀而模糊不清&#xff1f;现在…...

接口测试中缓存处理策略

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

网络六边形受到攻击

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

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...