首页 > 其他分享 >浅谈 树上带权最长最短路径,决策包容性与点分树

浅谈 树上带权最长最短路径,决策包容性与点分树

时间:2023-05-24 14:34:55浏览次数:61  
标签:分树 路径 浅谈 dep 分治 查询 带权 lca 树上

树上带权最长最短路径,决策包容性与点分树

\(\text {preface}\)

最近学习了点分树相关的内容,也碰巧见识到了许多……树上路径问题(非负权),最长或是最短,有的可以用点分治(树)解决,有的可以用 线段树解决,有的需要深层次挖掘性质,就在这里做一个小小地总结了一些另类的方法。

1.树上带权最长路径

规律 \(\text {i}\) :

带修最长路径问题往往可以通过 \(dfs\) 序转化为 在线段树上维护 \(a_x+b_y+c_z(x < y \leq z)\) 最值的问题。

或者说,带权树直径……?

这个其实是在我思考…… luogu P7565 的一个愚蠢至极的做法的时候理解的。

引入:

给出一棵树边权为 \(1\),有点权,定义 \(D(u,v) = dis(u,v)+w_v\),定义每个点 \(u\) 的树半径为 \(\max D(u,x)\),你需要支持修改点权,查询所有点树半径的最小值。

将半径问题转化为直接问题,可以证明半径最小值等于带权树直径的一半,于是维护树的直径,\(\max_{u,v} (w_u+w_v+dis(u,v))\)。

树上一条路径的长度可以被表示为 \(dep_u + dep_v-2dep_{lca}\),同时在 dfs 序上将路径拆分,(dfs序 求LCA)表示为 \((u,v]\) 中最浅的点的父亲。

所以尝试将路径表示为 \(dep_i - 2depfa_j + dep_k (i < j \leq k,\text{j 是 (i,k] 中深度最小的点})\) 的形式,其中 \(depfa\) 表示父亲的深度。

\(\text {lca}\) 或者说深度最浅的点这个限制的存在让我们难以维护,但是由于我们要求的是 \(\max\),所以对于一组 \((i,k]\) 我们选择的 \(j\) 如果不是最浅的,那么这样一定不优,因为会让减的 \(dep\) 变大,我们对这种并不正确的统计有包容性,这样是不影响答案的,所以可以直接维护 形如 \(dep_i - 2depfa_j + dep_k (i < j \leq k)\) 的形式。

本题中就维护 \(dep_i + w_i - 2depfa_j + dep_k + w_k (i < j \leq k)\),就行了,可以支持单点修改。

维护的方式就是和 \(a_x + b_y + c_z(x<y<z)\) 一样的,维护 \(a_x,b_y,c_z,a_x+b_y(x<y),b_y+c_z(y<z)\),这个东西显然可合并拼接。

*题目出处:CF1783 G.Weighed Tree Radius ,本题官方题解是线段是分治维护直径,常数大且不能在线。

例:

给你一棵树,带边权和点权,距离的定义 \(D(u,v) = w_u+w_v+dis(u,v)\),每次询问离一个点距离最大的点,支持修改边权和点权和加叶子。

加叶子就是个诈骗操作,离线了等于没有,

还是把路径拆成类似的形式,接下来我们要查的就是 \(dfs\) 序 在 \(u\) 前 \(u\) 后 分别查一下 \(dep_i + w_i - 2depfa_j(i<j)\) 和 \(- 2depfa_j + dep_k + w_k(j\leq k)\) 的最大值就行了,然后修改点权是平凡的,修改边权其实就是给 \(dep\) 做区间加,给 \(depfa\) 做一个区间加和一个单点修改。

题目来源:原创,感觉还行,虽然好像直接 LCT makeroot 模拟就行……?。

再举一个很蠢的例子,给一棵无根树对于每个 \(x\),找出两个 \(siz \geq x\) 且距离最远的不交子树。

先给树定个根,然后对于 有祖先关系的,直接 dfs 序上取 \(\min\) 或者求 \(\min\) 就行了,接下来考虑没祖先关系,这个时候就可以直接用 \(siz\) 了,把点 \(siz\) 从小到大加进去,然后就是类似刚刚的问题了,为了避免出现祖先关系,加入一个点之后把已经加入的祖先全部都设为不可用(正无穷)就行了,祖先一定在父亲被更新过了,所以只用更新父亲就行。

*题目出处:简化后的 JOISC 2021 Day3

2.树上带权最短路径

规律 \(\text {ii}\) :

带修最短路径问题可以考虑点分治(树),枚举分治中心作为路径上的点,将路径拆分成两半处理,这类问题往往可以转化为在点分树上子树内的最近点的查询。

引入:

如何给出一棵树(权值均非负),对于每个点 \(u\) 求 \(\min_{v\neq u} {dis(u,v)+w_v}\)?

这个问题并不困难,很容易想到用点分治解决,我们只需要对树进行质心分治,每次分治的时候处理所有过点 \(x\) 的路径,在计算时保留离分治中心最短及次短的路径就行了。

那么 动态修改 + 询问呢 ,例如修改一条边权或者点权,查询点权值。

这个时候就要使用点分树(动态点分治)了,将路径从点分树上的公共祖先拆成两部分 \(u \to \operatorname{lca}(u,v),\operatorname{lca}(u,v) \to v +w_v\),即枚举这条路径在点分治的哪一层被统计到的,然后接下来就要对于这个 \(\operatorname{lca}\),求出 和 \(u\) 不在同一子树的 \(v\) 的距离的最小值,这是难以统计的,因为这个信息 不同于模板中的点权和,并没有可减性*。

*:点分树 在统计的时候往往要查询在 \(LCA\) 子树且不在 \(u\) 子树中的所有 \(v\) 的信息,这个形状在树上是很畸形难以维护的,往往需要利用信息的可减性或是包容性,我们稍后会谈到。

但是发现,我们可以不管和 \(u\) 不在同一子树这一限制,因为即使在不是 \(\text{lca}\) 统计了,也不会影响答案,因为在不是 \(\text {lca}\) 的点 \(X\) 统计,能够选择的 \(v\) 集合一定不会更大,因为在原树上的路径相当于多出了一段非负的长度 \(u \to x \to X \to x \to v\) 可以查询的集合也就更小了,我们把这种性质称作决策包容性。

决策包容性使得我们可以查询一个更完整的形态的集合,其中某些点一定不影响答案,这样在本题中,我们可以直接查询这整棵子树中最优秀的点,可以直接用数据结构维护。

点分树也使得一次修改 只需要考虑那 \(\log\) 次分治时 \(x\) 到所选的分治中心所受到的影响,所以可以直接在 \(\log\) 次中修改,在这道题中对边权的修改本质也是相同的,只需要拿线段树维护子树距离加减就行了,复杂度 \(O(n+q\log^2n)\)。

*题目出处:PA2017 Banany,本题官方题解为树链剖分后维护启发式暴力维护轻子树信息,也有优雅的根号重构做法,值得一看。

例:

给出两棵树 \(T1,T2\) ,定义两个点的距离 \(D(u,v)\) 为标号 \(u\) 的点和标号 \(v\) 的点在两棵树上的距离和,对于每个点,求 \(D\) 距离最小的点,\(2.5\times 10^5\)。

有一个部分分是 T2 是一条链。

这个部分分还是蛮显然,启发我们对 \(T1\) 进行点分治,查询,把链上距离的绝对值拆开,查询 \(dis - x\) 和 \(dis + x\) 最近点就行了。

那么如果 T2 是一棵树呢?

我们显然不能 再枚举了,因为树上的路径关系是不能用简单的 左,右 来描述,常见的描述方式还是将路径从路径上一个点拆开,即点分治,我们考虑建出 T2 的点分树,然后查询时,枚举两个点在 \(T2\) 点分树上的 LCA,然后在这 \(\log\) 个点统计一下路径。

然后还是会有刚刚一样的问题:我们需要在 LCA 处统计,这很困难,因为我们需要要求 \(v\) 不在 \(lca\) 处 \(u\) 的子树中,但是因为边权非负,那些不在 \(lca\) 处被统计的点一定是不优的,路径一定变成了 \(u \to x \to X\to x \to v\) 的形式,这样统计到的点一定是不会影响答案的,于是我们可以直接查询 子树内和 \(LCA\) 最近的点就行了。

*题目出处:XX Open Cup Korea K.Wind of Change,本题官方

于是我们可以把带有这种,查询在 \(LCA\) 子树且不在 \(u\) 子树中的所有 \(v\) 的信息,通过包容性或者可减性(模板题中查询 \(LCA\) 子树再减去 \(u\) 子树),转化为子树查询,这是一个形态完整的集合,往往可以用数据结构维护。


废话:

文化课好痛苦。

好像把我巨大的名字插进省队小小的名单里啊.jpg……?

标签:分树,路径,浅谈,dep,分治,查询,带权,lca,树上
From: https://www.cnblogs.com/Dreamerkk/p/17428200.html

相关文章

  • 浅谈TCP协议的发生过程
    1.TCP协议1.1TCP协议的性质面向连接的、可靠的、基于字节流至于为什么面向连接,又为什么可靠,基于字节流的,等后面便可知道.1.2TCP协议栈收发数据的四个阶段创建套接字连接服务器收发数据断开服务器连接,删除套接字1.3TCP头部格式2.创建套接字2.1首先理解......
  • 浅谈POI数据在互联网旅游领域中的应用(一)
    首先了解下,什么是POI?POI是英文"PointofInterest"的缩写,直译过来叫“兴趣点”,有的人也叫它“信息点”。简单来说就是可以用经纬度表示的、对人有意义的地图上的点。我们平时使用滴滴打车的上车地点、使用大众点评发掘的各种餐厅、你家楼下的公共厕所,只要对你有意义,都可以算POI数据......
  • 2020校招生面试浅谈
    最近在招聘校招生,也看了很多简历,结合自己面试的经历,简单聊聊校招生该如何准备面试。一个漂亮的简历简历首先要漂亮,至少要有一定的美化和包装,对于校招生来说,学校教育背景、学习成绩是最重要的,项目和实习则是锦上添花。对于项目和实习经验,个人觉得有即可,不要求非常的好,不一定要去世界......
  • 浅谈同余3(扩展中国剩余定理,扩展BSGS)
    距离上一篇已经四个月了,我来填坑了上一篇:$浅谈同余2(扩展欧几里得,中国剩余定理,BSGS)$(https://www.cnblogs.com/xyy-yyds/p/17418472.html)0x50扩展BSGS$O(\sqrtn)$【模板】扩展BSGS/exBSGS 题目背景题目来源:SPOJ3105Mod题目描述给定$a,p,b$,求满足$a^x≡b\pmodp......
  • 浅谈同余1(常用定理和乘法逆元)
    点个赞吧,球球了~下一篇:$浅谈同余2(扩展欧几里得,中国剩余定理,BSGS)$https://www.acwing.com/file_system/file/content/whole/index/content/7882318/ $\LaTeX$太多了,分成几个部分0x00总写(瞎说)同余是数学中非常重要的东西,这里会写出同余的基本运用若$a\bmodm=b\bmo......
  • 浅谈物联网平台的重要性以及建设展望
    随着物联网(InternetofThings,简称IoT)技术的快速发展,物联网平台已成为连接各种设备,处理大量数据,并为用户提供智能服务的关键工具。在此背景下,深入理解物联网平台的重要性,以及对其未来建设的展望显得尤为重要。物联网平台在链接设备、管理数据以及提供服务等方面具有重要价值:在设......
  • 浅谈 OI 中各种合并操作
    前言合并操作一直是OI中一大考点,今天请各位跟着笔者来梳理一下各种合并操作。启发式合并几乎可以说是最经典的合并了。假定我们可以在\(O(k)\)的时间内往某个集合中插入一个数,那么我们就可以在\(O(n\lognk)\)的时间内合并若干个元素总量为\(n\)的集合。集合启发式......
  • 浅谈一类信息的暴力重构手法
    loj#6515.「雅礼集训2018Day10」贪玩蓝月背包支持类似栈的加入与撤销(由于是最优化,不太能直接删除),而题目要求维护双端队列式的操作,这是一个经典问题——双栈模拟双端队列(也叫bakatrick)。直接给出方法:维护两个栈,两栈的拼接即为我们维护的队列,照常进行大部分操作,若某一栈在空......
  • 浅谈Java SE、Java EE、Java ME三者的区别
    现在一个个来分析 1.JavaSE(JavaPlatform,StandardEdition)。JavaSE以前称为J2SE。它允许开发和部署在桌面、服务器、嵌入式环境和实时环境中使用的Java应用程序。JavaSE包含了支持JavaWeb服务开发的类,并为JavaPlatform,EnterpriseEdition(JavaEE)提供基础。 2.Java......
  • 浅谈Javascript 中几种克隆(clone)方式
    一:在Javascript里,如果克隆对象是基本类型,我们直接赋值就可以了:Js代码varsStr="kingwell";varcStr=sStr;alert(cStr);//输出kingwellsStr="abc";alert(cStr);//输出kingwell; 把一个值赋给另一个变量时,当那个变量的值改变的时候,另一个值不会受到影响。 ......