algorithm - 在无根树中查找多个 LCA

Question

我正在尝试为无根树实现 LCA。我给出了一棵树（一个无环的连通无向图）和一系列关于 LCA 的查询，用于一些根和两个顶点。每个特定的查询都可以有不同的根，所以我不能使用在一开始就为任意根预处理树的算法。

到目前为止，我已经尝试使用 DFS 找到从两个顶点到根的路径，然后检查它在哪里发散，但它有点慢（O（nq），其中 q 是查询数）。

有什么建议如何预处理树以获得查询的次线性复杂性？

Answer 1

令 LCA(u, v, w) 是 v 和 w 关于根 u 的 LCA。为了计算 LCA(u, v, w)，我们可以计算，对于任何固定的 r，

LCA(r, u, v)
LCA(r, u, w)
LCA(r, v, w)

并取出“奇怪的人”，即如果两个相等而第三个不同，则取第三个，否则它们都相等，所以取那个节点。

Answer 2

以任意顶点为根并对树进行 LCA 预处理。对于每个查询 (u,v) 和 r 作为根，设 w 是树中 u 和 v 的 LCA。

• 如果 w 在 r 的子树中，那么 w 就是答案。
• 如果 r 在 w 的子树中，那么 r 就是答案。
• 如果 r 在 u 或 v 的子树中，则对应的顶点就是答案。