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

Space Complexity graph

Pareto Decades graph