树上动态节点集最大距离查询 各操作O(log n)实现咨询

问题定义 #

给定一棵任意结构的树T，初始状态下选中节点集合P = {}为空，需要支持三类操作，要求累计q次操作的整体时间复杂度为O(q log n)，即每个单次操作的耗时不超过O(log n)级别：

• 将指定节点添加到集合P
• 将指定节点从集合P中移除
• 查询集合P内任意两节点的最大距离（即集合P在树上诱导子图的直径长度）

现有已验证的实现思路 #

在纯插入场景下，已经跑通了低复杂度的维护逻辑：

全程跟踪维护集合的最大距离值，记录构成最大距离的两个端点a、b。
插入新节点时，仅需计算新节点与原有两个端点的距离，对比原有最大距离值，取三者最大值作为新的最大距离，同步更新对应的端点即可。
查询操作直接返回记录好的最大距离值，不需要重复计算。
这套逻辑配合预处理完成的倍增LCA结构计算两点距离，插入和查询操作的单次复杂度刚好可以达到O(log n)的要求。

当前的实现卡点 #

上述简化逻辑在删除场景下完全失效：
如果没有额外结构做信息支撑，常规重新求解集合最大距离的方法需要遍历集合内所有节点，整体复杂度达到O(n)，完全达不到要求的效率标准。

复杂度达标的删除实现方案 #

存在成熟的实现方法可以满足O(log n)的单操作复杂度要求，核心是跳出仅靠两个直径端点维护全局极值的简化逻辑：

• 预处理阶段完成树的深度标记、LCA倍增表构建，将任意两点的距离查询耗时压缩到O(log n)单次水平
• 结合动态平衡树对集合内节点做结构化存储，替代直接遍历的统计逻辑：将集合内节点按照深度值、到根节点的路径长度等关键维度排序存储，在节点发生插入、删除动作时，同步更新平衡树内关联的极值信息，所有节点的增删、极值查询动作都可以在O(log n)时间内完成
• 删除节点时不需要重新遍历全集合计算直径，直接从平衡树维护的极值索引中取出当前集合的最大距离值即可，全程耗时不会超过O(log n)的约束。

内容的提问来源于stack exchange，提问作者Ehsan Gerayli