cie*_*woj 4 algorithm tree least-common-ancestor lowest-common-ancestor
我正在尝试为无根树实施LCA.我已经给出了一个树(一个没有循环的连通无向图)和一些关于某些根和两个顶点的LCA的查询.每个特定的查询都可以有不同的根,所以我不能使用在开始时对任意根进行预处理的算法.
到目前为止,我已经尝试使用DFS找到从顶点到根的路径,然后检查它在哪里发散,但是它有点慢(O(nq),其中q是查询数).
有任何建议如何预处理树,以便具有查询的次线性复杂性？
设LCA(u,v,w)是关于根u的v和w的LCA.为了计算LCA(u,v,w),我们可以计算任何固定的r,
LCA(r, u, v)
LCA(r, u, w)
LCA(r, v, w)
并取出"奇怪的人",即,如果两个是相等的而第三个是不同的,那么取第三个,否则它们都是相等的,所以取这个节点.