# Least common ancestor relative to an arbitrary vertex as root

Consider following problem:

Given an undirected tree answer following type of queries. (No. of queries and vertices can be as high as $$10^5$$)

$$\text{LCA}(r, u, v)$$: Find the Lowest Common Ancestor of vertices $$u$$ and $$v$$ assuming vertex $$r$$ as the root.

Now, in solution it's given that answer will always be one this: $$r, u, v, \text{LCA}(r, u), \text{LCA}(r, v), \text{LCA}(u, v).$$

Where $$\text{LCA}(u,v)$$ denotes Lowest Common Ancestor of vertices $$u$$ and $$v$$ if we assume vertex number $$1$$ as the root.

So I'm looking for a proof for claim made in a solution.

## 1 Answer

Let us consider several possibilities:

• The root is $$r$$. In this case, $$\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v)$$.
• The root is $$u$$, and $$r,v$$ are contained in different branches. In this case, $$\mathrm{LCA}(r,u,v) = u$$.
• The root is $$u$$, and $$r,v$$ are contained in the same branch. If $$r$$ is an ancestor of $$v$$, then $$\mathrm{LCA}(r,u,v) = r$$. If $$v$$ is an ancestor of $$r$$, then $$\mathrm{LCA}(r,u,v) = v$$. Otherwise, $$\mathrm{LCA}(r,u,v) = \mathrm{LCA}(r,v)$$.
• The root is none of $$r,u,v$$, and all of $$r,u,v$$ belong to different branches. In this case, $$\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v) = 1$$.
• The root is none of $$r,u,v$$, the vertex $$r$$ belongs to one branch, the vertices $$u,v$$ to another. In this case, $$\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v)$$.
• The root is none of $$r,u,v$$, the vertex $$u$$ belongs to one branch, the vertices $$r,v$$ to another. In this case, $$\mathrm{LCA}(r,u,v) = \mathrm{LCA}(r,v)$$.
• The root is none of $$r,u,v$$, and all of $$r,u,v$$ belong to a single branch, say rooted by a child $$s$$ of $$r$$. We apply induction to the subtree rooted at $$s$$.

To convince yourself of the various claims, I suggest drawing some diagrams, and using the characterization of $$\mathrm{LCA}(r,u,v)$$ as the vertex on the unique path from $$u$$ to $$v$$ which is closest to $$r$$.

• I understood most of the proof. But I think in first case i.e when root is $r$ then answer will be $\text{LCA}(u, v)$ not $r$. Commented Apr 9, 2020 at 2:52
• I think you’re right! Thanks for noticing. Commented Apr 9, 2020 at 7:31