我正在尝试为无根树实现 LCA。我已经给出了一棵树(一个没有循环的连通无向图)和一系列关于一些根和两个顶点的 LCA 的查询。每个特定的查询都可以有不同的根，所以我不能使用在开始时为任意根预处理树的算法。
到目前为止，我已经尝试使用 DFS 找到从两个顶点到根的路径，然后检查它在哪里 fork ，但它有点慢(O(nq)，其中 q 是查询数)。
关于如何预处理树以获得次线性查询复杂度的任何建议？
最佳答案
设 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)
然后取出“奇怪的人”，即如果两个相等而第三个不同，则取出第三个，否则它们都相等，所以取出那个节点。
关于algorithm - 在无根树中查找多个 LCA，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25371865/