1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Vimal Patel Apr 9 at 2:52
  • $\begingroup$ I think you’re right! Thanks for noticing. $\endgroup$ – Yuval Filmus Apr 9 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.