Наименьший общий предок с помощью разреженной таблицы

В этом уроке

• Построим эйлеров обход и сведём запросы LCA к запросам минимума на отрезке.
• Применим разреженную таблицу, чтобы отвечать на запросы LCA за $O(1)$.

Наименьший общий предок

Наименьший общий предок (lowest common ancestor, LCA) вершин $u$ и $v$ — это их общий предок с наибольшей глубиной. Вершина считается своим собственным предком.

Построение эйлерова обхода

Во время обхода в глубину (DFS) записываем каждую вершину при входе в неё. После возвращения из сына записываем родителя снова.

Эта последовательность называется эйлеровым обходом.

Для каждой вершины $v$ храним:

• $d_v$: её глубину, причём .