Lowest Common Ancestors with Linking and Cutting (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 on-line. Interspersed with the queries are on-line commands of two types: $link(x, y)$, where $y$ but not necessarily $x$ is a tree root, and $cut (x)$, where $x$ is not a root. The effect of a command $link(x, y)$ is to combine the trees containing $x$ and $y$ by making $x$ the parent of $y$. The effect of a command $cut (x)$ is to cut the edge connecting $x$ and its parent, splitting the tree containing $x$ into two trees: one containing all descendants of $x$ and another containing all nondescendants of $x$.
Generalizations: Lowest Common Ancestor
$n$: number of vertices
$m$: number of total number of operations (queries, links, and cuts)
Table of Algorithms
Currently no algorithms in our database for the given problem.