Tarjan's Off-line Lowest Common Ancestors Algorithm

Tarjan's off-line lowest common ancestors algorithm is a computer science algorithm for computing the lowest common ancestor of pairs of nodes in a tree, built on the union-find data structure; the lowest common ancestor of two nodes is the ancestor of both that has the greatest depth in the tree. It is named after Robert Tarjan, who discovered the technique in 1979, and it is described as offline because every pair of nodes whose lowest common ancestor is wanted must be specified in advance, unlike other lowest common ancestor algorithms. Its simplest version runs on the union-find data structure, which can take more than constant time per operation when the number of queried pairs is comparable to the number of nodes, and a later refinement by Gabow and Tarjan in 1983 sped the algorithm up to linear time.