别样的 O(1) LCA

· · 休闲·娱乐

Part1：结论

假设根节点为 rt，点 u,v 之间的距离为 \operatorname{dis}(u,v)。我们可以惊人的发现 \operatorname{lca}(u,v) 满足如下性质：

当且仅当 \operatorname{dis}(u,w)+\operatorname{dis}(v,w)+\operatorname{dis}(rt,w) 达到最小值时，w=\operatorname{lca}(u,v)。

证明：

显然可以得到：

可以得到 w 是 \operatorname{lca}(u,v) 当且仅当 w 同时在路径 u\to v,u\to rt,v\to rt 上（具体证明后面会讲），所以此时上述三个式子都取到最小值，即 2\operatorname{dis}(u,w)+2\operatorname{dis}(v,w)+2\operatorname{dis}(rt,w) 达到最小值，所以 w=\operatorname{lca}(u,v) 当且仅当 \operatorname{dis}(u,w)+\operatorname{dis}(v,w)+\operatorname{dis}(rt,w) 达到最小值。

Part2：求法

有了这个结论后，如果我们使用 O(1) 求 \operatorname{dis}，就可以做到 O(n) 求 \operatorname{lca}，可以得到和暴力一样的复杂度。

考虑建出点集 \{u,v\} 的虚树，按照我们平时建虚树的习惯，我们刚好会将根节点也加入进去，惊人的发现此时虚树中恰有四个点 u,v,rt 和一个新的节点 w，接下来我们证明 w=\operatorname{lca}(u,v)：

首先不难得到 w 是路径 u\to v 中的点，其次由于虚树上连边的点仍然具有原树上的祖先关系，所以 w 是 u,v 的祖先，即 w 在路径 u\to rt,v\to rt 上。

此时，由于 w 同时在 u\to v,u\to rt,v\to rt 三条路径上，所以此时显然可以得到 \operatorname{dis}(u,w)+\operatorname{dis}(v,w)+\operatorname{dis}(rt,w) 取到最小值，所以 w=\operatorname{lca}(u,v)。

由于我们只需要对 O(1) 个点建虚树，所以我们使用 O(\text{点数}) 建虚树即可得到一个 O(1) 的求 \operatorname{lca} 方法。

这种求 \operatorname{lca} 的方法具有一种优势，只要我们稍稍修改一下虚树的结构即可轻松地支持换根。

Part3：总结

本文使用循环论证、虚树等技巧给出了一种支持换根的 O(1) 求 \operatorname{lca} 方式。

恰好虚树现在已经加入最新最热 NOI 考点，大家可以以此作为一个不错的练习。