algorithmtreeleast-common-ancestorlowest-common-ancestor

Find multiple LCAs in unrooted tree

I am trying to implement LCA for unrooted tree. I have given a tree (a connected undirected graph without cycles) and a sequence of queries about LCA for some root and two vertices. Every particular query can have different root, so I cannot use algorithms that preprocess the tree for arbitrary root at the beginning.

So far I've tried to find paths from both of vertices to the root with DFS and then check where does it diverge, but its somewhat slow (O(nq), where q is number of queries).

Any suggestions how to preprocess the tree in order to have sublinear complexity of query?

Solution

  • Let LCA(u, v, w) be the LCA of v and w with respect to root u. To compute LCA(u, v, w), we can compute, for any fixed r,

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

    and take the "odd man out", i.e., if two are equal and the third is different, then take the third, else they're all equal, so take that node.