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

[学习笔记]虚树

前言&&思想

一些给定树上一些点集,要处理和该点集有关的询问(例如和点集关系,点集选择限制)的题目,

很多子树没有变化,暴力没有意义。

提取出有关的点和路径,构成虚树

虚树上DP等等,难点往往在于找到非虚树部分的答案。

 

建立

1.暴力sort再sort

LCA一般都要用,所有点按照dfn序sort,相邻两点的LCA就是所有涉及到的LCA

注意,LCA可能算重!

然后所有的点(包括LCA)再按照dfn sort

利用括号序,用栈模拟,如果新来的点不在栈顶的子树范围内[dfn,dfn2]就弹出栈顶

2.LCT,还支持换根

换根LCA:以r为根,a,b的lca为lca(a,b)lca(a,r)lca(b,r)(伪LCA会被计算两次就消了)

换根dfn序:可以分类讨论子树范围,但是,虚树要sort,你怎么重载小于号?必须有dfn序,,但是不能立刻求出来。

所以,换根大师LCT闪亮登场!

 

设当前根是rt

access每个点

恰好连到和rt在一条链上就停止,在这个点上打标记

最后找每个点到根路径上第一个有标记的点,就是这个点的父亲。

复杂度还是logn,常数大

 

 

 

例题

保卫王国加强版

对n个点进行限制

 

把转移变成矩阵

然后倍增维护

和动态DP有相似之处

消耗战

 [SDOI2011]消耗战

世界树

 [HNOI2014]世界树

WC2018 通道

学了边分治再写

Codechef Sad Pairs加强版

• 给出一张图,每个点都有颜色
• 对每个点求出
• 如果把这个点从图中删去
• 那么会有多少对不连通的同色点对
• ?, ? ≤ 10^7(原题是2e5)

 

删点不连通,点双,圆方树 

非割点:没有影响

割点:子树DP一下

有不同颜色,所以建立虚树(这里sort可能要松式排序,,,)

在圆方树上dfs时候

如果当前点是割点

1.统计当前颜色虚树上的不连通点对,树形DP即可

2.统计所有颜色的虚树上的不连通点对。。。。

一个麻烦事是,虚树上一条边上选择一个原树割点,都会对这个虚树造成相同的影响(两边sz乘积)

n,m 1e7不能带log

所以就树上差分了

设虚树上,(x,y)的边,x是y的父亲

原树上,x的位置减去贡献,y的原树father位置加上贡献

最后dfs扫一遍就行了。

Codechef BTREE

给出一棵树
每次询问给出一个集合,集合中的元素为 ?, ? ,表示标记了所
有距离 ? 不超过 ? 的点,你需要求出一共标记的多少点(一次或
多次)
?, ? ≤ 10^5

暴力点分治可以在O(logn)时间求出距离x为d的点的个数

CodeChef Union on Tree (虚树+点分治)

 

建立虚树

然后计算每个点实际能辐射覆盖的最大范围(树形DP一下)(可能来自比较远的辐射中心)

但是显然会算重

考虑对于每个点去重

画图(x,y),x是y的父亲

 

二分出这个mid,使得y在mid的位置恰好大于等于x在mid的位置的覆盖范围

如果mid位置,两边还能覆盖的范围都是r0,减去距离x为r0的点的个数即可

否则,必然有x覆盖范围比y的多1,大概是这样的图形:

 

对于中间两个三角形,就是都不能往对面扩展形成的

 对于2,就是子树里距离不超过d的点的个数,主席树即可

对于1,距离计算不超过d的点的个数,然后往y走一步(也就是到mid位置),再减去mid子树距离不超过d-1的点的个数

 

还有一些其他情况:
1.范围不交

2.x或者y的r等于0

3.mid位置是x或者y

结合

动态DP

整体DP

 

转载于:https://www.cnblogs.com/Miracevin/p/10372049.html

相关文章:

  • Iterator 和 for...of 循环
  • SharePoint:如何使用PowerShell批量删除名称以XXX开始的List?
  • Kafka之与Spring集成
  • python 模块一览
  • 《流浪地球》:一个程序员用代码拯救了世界,真硬核!
  • 500位软件开发工程师的声音:微服务和CI/CD依旧是最爱
  • 机器学习进阶-图像形态学操作-膨胀操作 1.cv2.dilate(进行膨胀操作)
  • 用Python写一份独特的元宵节祝福
  • Java开源诊断工具 Arthas 发布v3.1.0
  • 汇编语言第一章检测题
  • 无法打开外网ip链接
  • vue 组件通信
  • vue 配置sass、scss全局变量
  • LeetCode 28.实现strStr()(Python3)
  • CODING 缺陷管理功能正式开始公测
  • [nginx文档翻译系列] 控制nginx
  • [NodeJS] 关于Buffer
  • 【跃迁之路】【669天】程序员高效学习方法论探索系列(实验阶段426-2018.12.13)...
  • crontab执行失败的多种原因
  • HTTP那些事
  • Java的Interrupt与线程中断
  • Just for fun——迅速写完快速排序
  • MySQL数据库运维之数据恢复
  • nodejs实现webservice问题总结
  • React系列之 Redux 架构模式
  • Redis中的lru算法实现
  • Spring Security中异常上抛机制及对于转型处理的一些感悟
  • 大快搜索数据爬虫技术实例安装教学篇
  • 那些年我们用过的显示性能指标
  • 前端自动化解决方案
  • 区块链分支循环
  • 深入浅出Node.js
  • 手机app有了短信验证码还有没必要有图片验证码?
  • 推荐一款sublime text 3 支持JSX和es201x 代码格式化的插件
  • 在 Chrome DevTools 中调试 JavaScript 入门
  • ​云纳万物 · 数皆有言|2021 七牛云战略发布会启幕,邀您赴约
  • # Java NIO(一)FileChannel
  • # Maven错误Error executing Maven
  • #100天计划# 2013年9月29日
  • #Lua:Lua调用C++生成的DLL库
  • #QT(TCP网络编程-服务端)
  • #传输# #传输数据判断#
  • $L^p$ 调和函数恒为零
  • (3)选择元素——(14)接触DOM元素(Accessing DOM elements)
  • (HAL库版)freeRTOS移植STMF103
  • (M)unity2D敌人的创建、人物属性设置,遇敌掉血
  • (Note)C++中的继承方式
  • (SpringBoot)第七章:SpringBoot日志文件
  • (附源码)springboot人体健康检测微信小程序 毕业设计 012142
  • (附源码)计算机毕业设计SSM智慧停车系统
  • (一)RocketMQ初步认识
  • (转)大型网站架构演变和知识体系
  • (轉貼) VS2005 快捷键 (初級) (.NET) (Visual Studio)
  • .NET WebClient 类下载部分文件会错误?可能是解压缩的锅
  • .NET/C# 阻止屏幕关闭,阻止系统进入睡眠状态