Lowest Common Ancestors with Linking and Cutting

Description

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

Related Problems

Generalizations: Lowest Common Ancestor

Related: Off-Line Lowest Common Ancestor, Lowest Common Ancestor with Static Trees, Lowest Common Ancestor with Linking Roots, Lowest Common Ancestor with Linking

Parameters

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