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

Ниже представлено описание задачи, приведены ссылки на сторонние ресурсы с материалами, а также на упражнения, которые можно решить для практики по данной теме.

Задача поиска наименьшего общего предка в общем виде формулируется следующим образом:

Пусть задано дерево $T$, подвесим его за некоторую вершину и назовём её корнем. Требуется для данных вершин $u$ и $v$ найти наиболее удалённую от корня дерева вершину, лежащую на обоих путях от $u$ и $v$ до корня.

Алгоритмы решения

Алгоритм $O(n)$ на построение, $O(n)$ на запрос

Описание тривиального алгоритма:

Обходом в глубину посчитаем глубину каждой вершины дерева. Напомню, что глубиной называется длина пути до вершины от корня дерева. Дальше для вершин $u$ и $v$ рассмотрим всех предков с одинаковой глубиной, из одинаковых предков возьмём ту вершину, глубина которой больше.

Очевидно, что сложность такого алгоритма $O(n)$ на предварительные посторения (обход в глубину), и $O(n)$ на запрос.

Алгоритм $O(n \log_2 n)$ на построение, $O(\log_2 n)$ на запрос

Одним из самых простых быстрых алгоритмов нахождения LCA является «Метод двоичного подъема». Почитать описание и посмотреть примеры реализации можно здесь:

• Викиконспекты - Метод двоичного подъема
• E-Maxx - Метод двоичного подъёма

Алгоритмы $O(n)$ на построение, $O(\log_2 n)$ или $O(\sqrt{n})$ на запрос

Алгоритмы, основанные на сведении задачи LCA к задаче поиска минимума на отрезке (RMQ). Почитать подробнее можно здесь:

• E-maxx - LCA к RMQ

Алгоритм $O(n)$ на построение, $O(1)$ на запрос (алгоритм Фарах-Колтона и Бендера)

• E-maxx - LCA за O(1)

Задачи

Простые

• Timus - 1471. Расстояние в дереве
• SPOJ - POLICEMEN

Средние

• Codeforces - 832D. Миша, Гриша и метро
• Timus - 1752. Дерево 2
• SPOJ - NTICKETS
• SPOJ - QTREE2
• SPOJ - DRTREE
• SPOJ - GRASSPLA

Сложные

• Codeforces - 733F. Недовольство автомобилистов
• Codeforces - 828F. Лучший вес для ребра
• Codeforces - 838B. Расходящиеся направления
• Codeforces - 1051F. Самое короткое условие