Lowest Common Ancestor (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$?"

Related Problems

Subproblem: Off-Line Lowest Common Ancestor, Lowest Common Ancestor with Static Trees, Lowest Common Ancestor with Linking Roots, Lowest Common Ancestor with Linking, Lowest Common Ancestors with Linking and Cutting

Related: Lowest Common Ancestor with Static Trees, Lowest Common Ancestor with Linking Roots, Lowest Common Ancestor with Linking, Lowest Common Ancestors with Linking and Cutting

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.

Time Complexity graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity graph

Error creating thumbnail: Unable to save thumbnail to destination

Pareto Decades graph

Error creating thumbnail: Unable to save thumbnail to destination