Find multiple LCAs in unrooted tree

Question

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?

Tesch

In this context, what exactly does LCA even mean? The "lowest" part of LCA usually can be inferred from the rootedness of the tree, but without that I'm not sure it's well-defined. Can you give an example or two? – Exposure

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. In every query I have given a vertex that is the root of the tree for this particular query, so I compute the LCA exactly as if the tree was rooted in this vertex. The difficulty of the problem is the tree can be rooted in different vertex for different queries, so I cannot preprocess it for any particular root, and cannot store for example pointers to the parent in the tree node, because the meaning of the parent can change in the next query. – Tesch

Thanks for clarifying! To confirm, your queries are of the form LCA(u, v, r), meaning "if the tree were rooted at r, what would the LCA of u and v be?" – Exposure

Yes, that is exactly what I meant. – Tesch

Answer 1

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.

Prelature

@sudeepdino008 I don't have it figured out any further than an unpleasant case analysis. – Prelature

Answer 2

Take an arbitrary vertex as root and preprocess the tree for LCA. For every query (u,v) and r as root, let w be the LCA of u and v in the tree.

• If w is in the subtree of r then w is the answer.
• If r is in the subtree of w then r is the answer.
• If r is in the subtree of u or v then the corresponding vertex is the answer.

Ardys