Tarjan's off-line least-common-ancestors algorithm is given as follows:LCA($u$)Make-Set($u$)Find-Set($u$).$ancestor$ = $u$for each child $v$ of $u$ in $T$ $\quad$ LCA($v$)  $\quad$ Union($u$,$v$)  $\quad$ Find-Set($u$).$ancestor$ $= u$  $u.color = $ BLACK  for each node $v$ such that $\{u, v\} \in P$  $\quad$ if $v.color == $ BLACK  $\quad \quad$ print The least common ancestor of u and v is Find-Set($v$).$ancestor$  Note that we are given a rooted tree $T$ and an arbitrary set $P = \{\{u,v\}\}$ of unordered pairs of nodes in $T$, and we want to determine the least common ancestor of each pair in $P$.  To solve the off-line least-common ancestors problem, the above procedure performs a tree walk of $T$ with the initial callLCA($T.root$).  Assume that each node is colored WHITE prior to the walk.Given this, prove that LCA (correctly) prints the least common ancestor of $u$ and $v$ for each pair $\{u,v\} \in P$.I'm thinking I'd need to prove two cases 1. w.l.o.g. $v \in T_u$ and 2. $v \notin T_u$ and $u \notin T_v$, where $T_u$ and $T_v$ are subtrees of $T$ rooted at $u$ and $v$, respectively.
Prove the correctness of Tarjan's off-line least-common-ancestors algorithm
algorithm analysis