树链剖分相关

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

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/790609.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

cdn中配置ssl证书

##red## &#x1f534; 大家好&#xff0c;我是雄雄&#xff0c;欢迎关注微信公众号&#xff0c;雄雄的小课堂。 SSL KEY 这个里面放的是&#xff1a;private.pem文件中的内容 SSL PEM 这个里面放的是&#xff1a;fullchain.crt文件中的内容&#xff0c;注意&#xff0c;这个…

JavaSE 面向对象程序设计进阶 IO流 字节流详解 抛出异常

input output 像水流一样读取数据 存储和读取数据的解决方案 内存中数据不能永久化存储 程序停止运行 数据消失 File只能对文件本身进行操作 不能读写文件里存储的数据 读写数据必须要有IO流 可以把程序中的数据保存到文件当中 还可以把本地文件中的数据读取到数据当中 分…

初学SpringMVC之 RestFul 风格、重定向和转发

RestFul 风格改变 URL 形式 比如之前是&#xff1a;http://localhost:8080/add?a1&b2 现在是&#xff1a;http://localhost:8080/add/a/b&#xff08;全是斜杠&#xff09; package com.demo.controller;import org.springframework.stereotype.Controller; import org…

ChatTTS的爆火是必然,它正在重新定义我们与机器对话的方式

当AI技术与语音合成相遇&#xff0c;开源技术众多&#xff0c;为什么 ChatTTS 能够一夜爆火&#xff1f;你有听说过能说情感真切文字的 AI 吗&#xff1f; 前言 想象一下&#xff0c;你只需输入一句话&#xff0c;AI就能念得声情并茂&#xff0c;不仅支持中英文混读&#xff0…

Webpack安装以及快速入门

3 Webpack 1 什么是Webpack https://webpack.js.org/ (官网) webpack 是一个现代 javascript 应用程序的 静态模块打包器 (module bundler) 待会要学的 vue-cli 脚手架环境, 集成了 webpack, 所以才能对各类文件进行打包处理 webpack是一个 静态模块 打包器,可以做以下的这…

一文彻底搞懂性能测试

性能测试概念 我们经常看到的性能测试概念&#xff0c;有人或称之为性能策略&#xff0c;或称之为性能方法&#xff0c;或称之为性能场景分类&#xff0c;大概可以看到性能测试、负载测试、压力测试、强度测试等一堆专有名词的解释。 针对这些概念&#xff0c;我不知道你看到的…

牛刀小试--下三角对称矩阵压缩存储

解析博客: 矩阵存储和特殊矩阵的压缩存储_n阶对称矩阵压缩-CSDN博客 函数功能: //为N阶下三角矩阵初始化成的一维数组分配空间 void Init_triangular_matrix(int *&matrix); //返回二维下三角矩阵的值(压缩存取) int get_Value_triangular_matrix(int matrix[],int x,int …

Canvas:实现在线画板操作

想象一下&#xff0c;用几行代码就能创造出如此逼真的图像和动画&#xff0c;仿佛将艺术与科技完美融合&#xff0c;前端开发的Canvas技术正是这个数字化时代中最具魔力的一环&#xff0c;它不仅仅是网页的一部分&#xff0c;更是一个无限创意的画布&#xff0c;一个让你的想象…

谷粒商城学习笔记-22-分布式组件-SpringCloud-OpenFeign测试远程调用

文章目录 一&#xff0c;OpenFeign的简介二&#xff0c;OpenFeign的使用步骤1&#xff0c;场景说明2&#xff0c;引入依赖2&#xff0c;开启OpenFeign3&#xff0c;编写Feign接口4&#xff0c;使用feign调用远程接口5&#xff0c;验证 错误记录 上一节学习了注册中心&#xff0…

Linux-shell编程入门基础

文章目录 前言Shell编程bash特性shell作用域变量环境变量$特殊变量$特殊状态变量 $特殊符号(很重要)其他内置shell命令shell语法的子串截取统计 指令执行时间练习shell特殊扩展变量父子shell的理解内置和外置命令区别 数值计算双括号(())运算letexprexpr模式匹配 bcawk中括号 s…

ts语法---泛型和泛型约束

泛型 泛型&#xff0c;动态类型&#xff0c;是一个初始化不明确的类型&#xff0c;类似于函数中的形参&#xff08;不明确参数值&#xff09;&#xff0c; 泛型一般用在function定义函数时动态约束类型&#xff0c;和type定义类型时动态约束类型&#xff0c; 泛型一般使用任…

Jenkins教程-18-常用插件-description-setter

上一小节我们学习了Jenkin常用插件Environment Injector的使用方法&#xff0c;本小节我们讲解一下Jenkin常用插件description-setter的使用方法。 在某些情况下&#xff0c;用户可能希望根据构建过程中的某些关键信息来自定义构建的描述&#xff0c;比如部署的用户信息、提交…

​李白一生的过往轨迹矢量地图

今天我们来看一下“天子呼来不上船&#xff0c;自称臣是酒中仙”大诗人李白过往轨迹&#xff0c;看看他一生都去过哪些地方&#xff1f; 我们将李白一生去过的地方搜集整理了一份矢量地图&#xff0c;有需要请在文末查看该数据的领取方法。 李白一生的过往轨迹 李白&#xf…

stm32按键设置闹钟数进退位不正常?如何解决

&#x1f3c6;本文收录于《CSDN问答解惑-专业版》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收…

JavaScript-日期对象

日期对象 作用&#xff1a;用来表示时间的对象 获取当前时间 const datenew Date();console.log(date);可以得到日期对象&#xff0c;里面的属性有星期&#xff0c;年月日&#xff0c;时分秒 获取指定时间 const datenew Date(2023-05-01);console.log(date); 获取时间戳 时间…

Deepspeed : AttributeError: ‘DummyOptim‘ object has no attribute ‘step‘

题意&#xff1a;尝试在一个名为 DummyOptim 的对象上调用 .step() 方法&#xff0c;但是这个对象并没有定义这个方法 问题背景&#xff1a; I want to use deepspeed for training LLMs along with Huggingface Trainer. But when I use deepspeed along with trainer I get …

实习记录3

1.Mybaits懒加载 MyBatis 延迟加载&#xff08;懒加载&#xff09;一篇入门-腾讯云开发者社区-腾讯云 (tencent.com) 2.高级映射 106-高级映射之多对一映射第一种方式_哔哩哔哩_bilibili 3.TableId(type IdType.INPUT) Mybatis-plus 主键生成策略_mybatis-plus 自增主键等于…

和鲸科技荣耀入选2024 H1 「中国最具价值 AGI 创新机构 TOP 50」

以下文章来源于Founder Park&#xff0c;作者Founder Par 大模型的盛宴&#xff0c;不应该只属于那些无数光环加身的算法天才们。 模型的冰山一角下&#xff0c;是应用层的暗流涌动&#xff0c;这是一个更庞大&#xff0c;也更隐秘的蓝海。但发掘这一切的前提是&#xff0c;所…

redis哨兵模式搭建

先搭建主从结构 当需要运行多个Redis实例时&#xff0c;可以通过为每个实例使用不同的配置文件的方式来实现。 复制redis目录下的redis.conf文件将其重命名为redis6380.conf和redis6381.conf&#xff0c;或者将其放到单独文件夹中&#xff0c;这里为了偷懒&#xff0c;简单实现…

使用 MinIO 赢得 RAG 权利

人们常说&#xff0c;在人工智能时代&#xff0c;数据是你的护城河。为此&#xff0c;构建生产级 RAG 应用程序需要合适的数据基础架构来存储、版本控制、处理、评估和查询构成专有语料库的数据块。由于 MinIO 采用数据优先的 AI 方法&#xff0c;因此对于此类项目&#xff0c;…