我正在尝试为无根树实现LCA。我给出了一棵树(一个没有周期的连通无向图)和一系列有关LCA的查询，这些查询有一些根和两个顶点。每个特定的查询都可以具有不同的根，因此我不能使用在开始时就针对任意根对树进行预处理的算法。
到目前为止，我已经尝试使用DFS查找从两个顶点到根的路径，然后检查它在哪里发散，但是有点慢(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/