$[$CLRS$,$ Problem $21-3,$ pages $584-585]$ Off$-$line Least Common Ancestors. The least common ancestor of two nodes u and v in a rooted tree T is the node w that is an ancestor of both u and v and that has the greatest depth in T with the above property. In the off$-$line least common ancestor problem, we are given a rooted tree T and an arbitrary set P $=\{\{$ui$,$ vi$\}|$ i$=1..$m$\}$ of unordered pairs of nodes in T$,$ and we wish to determine the least common ancestor of each pair $\{$ui$,$ vi$\}$ in P$.$

To solve the off$-$line least common ancestors problem, the following procedure performs a tree walk of T with the initial call LCA$($root$[$T$]).$ Each node is assumed to be coloured WHITE prior to the walk.

LCA$($u$)$

$1$ MakeSet$($u$)$

$2$ ancestor$[$Find$($u$)]$ u

$3$ for each child v of u in T do

$4$ LCA$($v$)$

$5$ Union$($Find$($u$),$ Find$($v$))$

$6$ ancestor$[$Find$($u$)]$ u

$7$ end$-$for

$8$ colour$[$u$]$ BLACK

$9$ for each node v such that $\{$u$,$v$\}$ in P do

$10$ if colour$[$v$]=$ BLACK

$11$ then print $$The least common ancestor of$$ u $$and$$ v $$is$$ ancestor$[$Find$($v$)]$

end

$($a$)$ Argue that line $11$ is executed exactly once for each pair $\{$u$,$v$\}$ in P$.$

$($b$)$ Argue that at the time of the call LCA$($u$),$ the number of sets in the forest of up$-$trees data structure is equal to the depth of u in T$.$

$($c$)$ Prove that LCA correctly prints the least common ancestor for each pair $\{$u$,$v$\}$ in P$.$

$($d$)$ Analyze the running time of LCA, assuming that we use the implementation with forest of up trees with balanced union and path compression.