View source for Lowest Common Ancestors with Linking and Cutting

{{DISPLAYTITLE:Lowest Common Ancestors with Linking and Cutting (Lowest Common Ancestor)}}
== 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.