Problem Statement
=================

In this chapter, we deal with a rooted tree and examine the following two problems on this tree.

.. The Problem of Ancestor at a Specific Height
-------------------------------------------

In this problem, a rooted tree with *n* vertices is given as input, followed by *q* queries. In each query, a vertex *v* and a number *h* are provided. It is guaranteed that the vertex's height is greater than *h*, and we are asked to find the **ancestor** of vertex *v* located at height *h* (which is unique).

The Problem of the Lowest Common Ancestor
-----------------------------------------

In this problem, a rooted tree with **n** vertices is given as input, followed by **q** queries. In each query, two vertices **v** and **u** are provided, and we are asked to find the lowest common ancestor (LCA) of these two vertices. The term *lowest common ancestor* is commonly abbreviated as **LCA**, which stands for *Lowest Common Ansector*.

The Relationship Between These Two Problems
--------------------

If we have a solution for the first problem that answers each query in :math:`O(x)`, we can answer each query of the second problem in :math:`O(x*lg(n))`.

LCA
Consider these two vertices. The ancestors above their height are common, and the lower ancestors differ. Therefore, we can perform a binary search on the height. To check if the ancestor at height x of these two vertices is common, we can obtain the ancestor at height x of both vertices using the first method and compare whether they are identical.