首页 > 其他分享 >[DS 小计] 点分树

[DS 小计] 点分树

时间:2024-04-10 20:04:50浏览次数:29  
标签:le dist log text 小计 点分 点分树 树上 DS

点分树是一个处理树上距离的优秀 DS。
它可以快速处理关于一些树上距离问题。

引入

我们知道,我们在做点分治的时候,每次找到中心,然后将重心所有的相连的边断开,处理子问题。时间复杂度是 \(O(n\log n)\) 的。

但是有些题目让我们搞强制在线,又要求距离为 \(k\) 的所有和,这时候点分树能起到一个很好的作用。

过程

构造一棵点分树的方法是,把每次点分治得到的根连起来,得到一棵虚树。
这棵树和点分治一样,有一些优秀的性质:

  • 树高不超过 \(\log n\)
  • 对于点分树上的 \(u,v\) ,若点分树上 \(lca\) 为 \(z\),原树上的 \(\text{dist}(u,v)=\text{dist}(u,z)+\text{dist}(v,z)\)
    这个证明很简单,因为 \(u,v\) 是在 \(z\) 的这个地方断开的,所以 \(z\) 一定在原树上 \(u\to v\) 之间。要不然它是怎么断开的呢(((

点分树的两个优秀性质就在此。
来看经典问题:给定 \(u,k\) ,求所有满足 \(\text{dist}(u,v)\le k\) 的 \(w_v\) 的和。
怎么做呢?令 \(z\) 为点分树上 \(u,v\) 的 \(lca\) 。
\(\text{dist}(u,v)\le k \Leftrightarrow \text{dist}(u,z)+\text{dist}(v,z)\le k\Leftrightarrow \text{dist}(v,z)\le k-\text{dist}(u,z)\)

所以,我们暴力枚举 \(z\) 即可。
所以我们开一棵动态开点线段树,记录所有 \(\text{dist}(x,z)\) ,表示这个点所有长度的情况。

然后暴力个更新查找。

但是有来自同一子树的两个点,这不能贡献,所以容斥记录一下,再开一棵动态开点线段树,记录 \(x\) 子树内每个点到 \(x\) 点分树父亲的距离的情况即可。

如果你写的很好,空间复杂度是 \(O(n\log n)\) 的。

你知道的,笔者太菜了,实现起来太细节,所以只实现了 \(O(n\log ^2 n)\)

标签:le,dist,log,text,小计,点分,点分树,树上,DS
From: https://www.cnblogs.com/g1ove/p/18127269

相关文章

  • 操作系统综合题之“采用二级页表的分页存储管理方式,计算页目录号的位数 和 页大小,给定
    一、问题:某计算机系统的主存按字节编址,逻辑地址和物理地址都是32位,其内存管理采用两级页表的分页存储管理方式。逻辑地址中页号位10位,页内偏移地址为10位。该计算机系统的两级页表结构如下图所示,图中数值均为十进制数1.页目录号的位数为多少?页的大小为多少KB?2.如果页目录项大小......
  • NL2SQL基础系列(1):业界顶尖排行榜、权威测评数据集及LLM大模型(Spider vs BIRD)全面对比
    NL2SQL基础系列(1):业界顶尖排行榜、权威测评数据集及LLM大模型(SpidervsBIRD)全面对比优劣分析[Text2SQL、Text2DSL]Text-to-SQL(或者Text2SQL),顾名思义就是把文本转化为SQL语言,更学术一点的定义是:把数据库领域下的自然语言(NaturalLanguage,NL)问题,转化为在关系型数据库中可以执行的......
  • 911-基于6U VPX的光纤图像DSP实时计算平台
    一、系统组成   该平台基于风冷式的6U6槽VPX图像处理平台,包括:计算机主板、计算机主板后板、存储板、图像信号处理板、图像信号处理板后板、图像光纤转接板、机箱背板及机箱组成。图1为系统背板结构示意图:  图1:系统背板互联示意图 备注:上图槽5板卡为太速自研的......
  • WDS+MDT网络启动自动部署windows(三)UEFI & BIOS 双PXE引导
    简介:我们可以通过调整启动文件来兼容不同的硬件(UEFI&BIOS),能否不手动调整呢?自动调整也是可以的。本来是是想将DHCP放在H3C5500上的,但是咨询过H3C的售前顾问后,没有任何一个型号支持这个功能,前面已经折腾过自动识别客户端类型,发送不同的启动文件了。为了更好的完成这个系列文章......
  • ADS1299模拟前端(AFE)代替料LHE7909
    今天我和大家分享一颗国产可以代替ADS1299的料——LHE7909,这是一颗由领慧立芯设计生产的一款具备颅外脑电图(EEG)和心电图(ECG)应用所需的全部常用功能的模拟前端芯片,并且凭借其高集成度和出色的性能,能够创建多种可扩展的医疗仪器系统,而尺寸,功耗和总成本却大大降低。以下是详......
  • GPT-4 Turbo 融合视觉能力;Google 新添 AI 视频应用 Vids丨 RTE 开发者日报 Vol.181
      开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(RealTimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑的个人观点......
  • MIPI DSI --- DCS(Display Command Set)
    MIPI协议族,定义了一个专门用于显示的命令集,叫做DisplayCommandSet,简称为DCS。屏幕制造商(屏幕驱动芯片)都使用这一套标准。DisplayArchitectures按照是否带有帧缓存,分为三种架构:不带帧缓存、带完整一帧的缓存、带一部分帧缓存。如果带了 Framebuffer,那么图形数据不用每次......
  • CPU、DSP、MPU、MCU、SOC、FPGA、ARM等概念
    CPU、DSP、MPU、MCU、SOC、FPGA、ARM等概念参考资料:百度知道“stm32和cortexm3是什么关系”:https://zhidao.baidu.com/question/178510430.html知乎“DSP与MCU与ARM与FPGA有什么区别?”:https://www.zhihu.com/question/278500219/answer/405183375CSDN“MCU和SOC的区别”:ht......
  • 洛谷题单指南-数学基础问题-P2926 [USACO08DEC] Patting Heads S
    原题链接:https://www.luogu.com.cn/problem/P2926题意解读:有n个数,计算每个数能整除其他数的个数。解题思路:a[100005]记录所有的数,h[1000005]记录所有数的个数,cnt[1000005]记录所有数能整除其他数的个数只需要读入a数组,同时更新h[a[i]]++再依次从小到大遍历h的下标每一个数i,如......
  • 解决 "last line of file ends without a newline" 警告的方法:使用 .editorconfig
    在软件开发过程中,我们经常会遇到一些常见的代码规范问题,其中之一就是"lastlineoffileendswithoutanewline"警告。这个警告表示文件的最后一行缺少换行符,可能会导致一些编辑器或版本控制系统的问题。如果每次都手动去操作添加一行有点麻烦,我们可以通过使用.editorconfig......