树上带权最长最短路径,决策包容性与点分树
\(\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