Lowest Common Ancestor with Linking Roots (Lowest Common Ancestor)
Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, The queries are given on-line. Interspersed with the queries are on-line commands of the form $link(x, y)$ where $x$ and $y$ are tree roots. The effect of a command $link(x, y)$ is to combine the trees containing $x$ and $y$ by making $x$ the parent of $y$.
Generalizations: Lowest Common Ancestor
$n$: number of vertices
$m$: number of total number of operations (queries, links, and cuts)
Table of Algorithms
|Modified van Leeuwen (Linking Roots)||1976||$O(n+m*log(log(n)$))||$O(n)$||Exact||Deterministic||Space|
|Harel, Tarjan (Linking Roots)||1984||$O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function||$O(n)$||Exact||Deterministic||Time & Space|