树链剖分相关
树链剖分这玩意儿还挺重要的,是解决静态树问题的一个很好的工具~
这里主要介绍一下做题时经常遇到的两个操作:
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老照片修复文字识别图像去雾一键抠图微信小程序源码
🔍解锁复古魅力,微信小程序黑科技大揭秘!老照片修复&更多神奇功能等你来试! 📸 【老照片修复,时光倒流的美颜术】 你是否珍藏着一堆泛黄的老照片,却因岁月侵蚀而模糊不清?现在…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...