别样的 O(logn) LCA

· · 休闲·娱乐

休闲娱乐交不了了，只有交算法理论了。

所需算法：二分。

假设我们现在需要求 u,v 的最近公共祖先 w，不难发现如果我们在 u\to w 的路径上选择一点 x，再从 v\to w 的路径上选择一点 y，那么 u\to v 的最短路径长度一定会减小，而它的逆定理也同样成立：如果在一棵树上连接两个点 x,y，如果 u\to v 的最短路径长度减小，那么 x,y 在 u\to w，或 v\to w。反之 x,y 至少有一个不在 u\to w 和 v\to w 上。

那么发现这个有什么用呢？注意到 u 和 v 的公共祖先是从 w 到根节点，满足单调性，所以可以采用二分。

我们从 u\to root 和 v\to root 分别取中点 p,q，连接 p,q，然后跑一次 bfs，判断此时的最短路径有没有变小，如果变小了，说明 \operatorname{lca}(u,v) 是在 p\to root 和 q\to root 的，否则就是在 p\to u 和 q\to v 上。重复进行操作，直到在一个点，单次复杂度为 n\operatorname{log}n，甚至比暴力还慢。

发现复杂度瓶颈在求路径长度，而我们可以把 u\to v 的路径变成 u\to p,p\to q,q\to v，而 u\to p,q\to v 都可以通过 deep(p) - deep(u)，deep(q) - deep(v) 求出来，p\to q 长度为 1，所以通过dfs，预处理 n 就可以轻松求出 p \to q 之间的新距离。

那么问题来了，怎么求原来的两个点之间的距离呢？需要 LCA。

除了求 LCA，这个求 LCA 的算法需要 n \log n，

不失为一种好的 LCA 求法。