Least common ancestor relative to an arbitrary vertex as root

Question

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.

Answer 1

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$.