Clever Geek Handbook

Find multiple LCAs in a pristine tree

I am trying to implement LCA for a rootless tree. I gave a tree (a connected undirected graph with no cycles) and a sequence of LCA queries for some root and two vertices. Each specific request may have different roots, so I cannot use algorithms that preprocess the tree for an arbitrary root at the beginning.

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

Any suggestions for a tree preprocessing for sublinear query complexity?

+3


source to share


2 answers


Let LCA (u, v, w) be the LCA of v and w with respect to the 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 person", i.e. if two are equal and the third is different then take the third, otherwise they are all equal, so take node.

+5


source


Take an arbitrary vertex as root and preprocess the tree for LCA. For each 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 r, then w is the answer.
  • If r is in a subtree of w, then r is the answer.
  • If r is in a subtree u or v, then the corresponding vertex is the answer.
0


source






More articles:


All Articles