Lowest Common Ancestor with Linking Roots

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

Parameters

$n$ : number of vertices
$m$ : number of total number of operations (queries, links, and cuts)

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

				See more
Harel, Tarjan [Linking Roots]	1984	O(n+ m*alpha(m + n, n)) where alpha is the inverse Ackermann function	O(n)
Modified van Leeuwen [Linking Roots]	1976	O(n+m*log(log(n)))	O(n)

Reductions Table

Insuffient Data to display table

Other relevant algorithms