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

\(\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\) 子树），转化为子树查询，这是一个形态完整的集合，往往可以用数据结构维护。