Наименьший общий предок (LCA): три способа найти за O(log n)

Коротко

LCA (lowest common ancestor) двух вершин дерева — самая глубокая вершина, которая является предком обеих.

Что это и зачем

            1
           / \
          2   3
         / \   \
        4   5   6
           / \
          7   8

LCA(7, 8) = 5
LCA(7, 4) = 2
LCA(7, 6) = 1

Задача выглядит академической, но у неё есть очень практичное следствие — расстояние между двумя вершинами дерева:

dist(u, v) = depth[u] + depth[v] − 2 · depth[LCA(u, v)]

Мы поднимаемся от u до общего предка и спускаемся к v. Путь до предка учтён дважды, поэтому его вычитаем удвоенным.

Отсюда применения:

• расстояния в дереве за O(log n) вместо O(n) на запрос;
• запросы на пути между вершинами (минимум, сумма, максимум);
• иерархии в базах данных: найти общего руководителя двух сотрудников, общую категорию двух товаров;
• системы контроля версий: общий предок двух веток при слиянии;
• биоинформатика: последний общий предок двух видов в филогенетическом дереве.

Наивный способ

Простейшая идея: поднимаем более глубокую вершину до уровня второй, потом поднимаем обе одновременно, пока не совпадут.

def lca_naive(parent: dict, depth: dict, u, v):
    # выравниваем глубины
    while depth[u] > depth[v]:
        u = parent[u]
    while depth[v] > depth[u]:
        v = parent[v]

    # поднимаемся вместе
    while u != v:
        u = parent[u]
        v = parent[v]

    return u

Работает, легко пишется, но каждый запрос стоит O(высоты дерева). На «бамбуке» из 10⁵ вершин и 10⁵ запросов это 10¹⁰ операций.

Двоичные подъёмы

Основной метод. Идея: вместо подъёма по одному шагу научимся прыгать сразу на 1, 2, 4, 8, … предков вверх.

Заведём таблицу up[v][k] — предок вершины v на расстоянии 2^k. Она строится по рекуррентности:

up[v][0] = родитель v
up[v][k] = up[ up[v][k-1] ][k-1]

Читается так: чтобы подняться на 2^k, поднимемся на 2^(k−1) дважды.

Любое расстояние раскладывается по степеням двойки — это просто двоичная запись числа. Значит подняться на произвольную высоту можно за O(log n) прыжков.

import math


class LCA:
    def __init__(self, tree: dict, root) -> None:
        self.n = len(tree)
        self.LOG = max(1, math.ceil(math.log2(self.n)) + 1)
        self.depth = {}
        self.up = {}      # up[v][k] — предок на 2^k выше

        self._dfs(tree, root, root, 0)

        # заполняем таблицу подъёмов
        for k in range(1, self.LOG):
            for v in self.up:
                self.up[v][k] = self.up[self.up[v][k - 1]][k - 1]

    def _dfs(self, tree, v, parent, d) -> None:
        # итеративный обход, чтобы не упереться в стек
        stack = [(v, parent, d)]
        while stack:
            v, parent, d = stack.pop()
            self.depth[v] = d
            self.up[v] = [parent] + [None] * (self.LOG - 1)

            for child in tree.get(v, ()):
                if child != parent:
                    stack.append((child, v, d + 1))

    def query(self, u, v):
        # 1. выравниваем глубины прыжками
        if self.depth[u] < self.depth[v]:
            u, v = v, u

        diff = self.depth[u] - self.depth[v]
        for k in range(self.LOG):
            if diff >> k & 1:            # k-й бит разности установлен
                u = self.up[u][k]

        if u == v:
            return u                     # одна оказалась предком другой

        # 2. поднимаем обе, пока предки различаются
        for k in range(self.LOG - 1, -1, -1):
            if self.up[u][k] != self.up[v][k]:
                u = self.up[u][k]
                v = self.up[v][k]

        return self.up[u][0]             # родитель — искомый предок

    def distance(self, u, v) -> int:
        return self.depth[u] + self.depth[v] - 2 * self.depth[self.query(u, v)]


tree = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6],
    4: [2],
    5: [2, 7, 8],
    6: [3],
    7: [5],
    8: [5],
}

lca = LCA(tree, root=1)
print(lca.query(7, 8))     # 5
print(lca.query(7, 4))     # 2
print(lca.query(7, 6))     # 1
print(lca.distance(7, 6))  # 5  → путь 7-5-2-1-3-6, то есть 3 + 2 − 2·0

Разбор второго этапа

Самая неочевидная часть — цикл, идущий от больших k к меньшим:

for k in range(self.LOG - 1, -1, -1):
    if self.up[u][k] != self.up[v][k]:
        u = self.up[u][k]
        v = self.up[v][k]

Логика такая. Мы поднимаемся настолько высоко, насколько можно, не доходя до общего предка. Если предки на высоте 2^k различаются — значит мы ещё ниже LCA, можно смело прыгать. Если совпали — прыжок был бы слишком большим, пропускаем.

В конце u и v стоят ровно на один уровень ниже LCA, и ответ — их общий родитель.

Порядок от больших степеней к меньшим обязателен: так мы жадно берём максимальные безопасные прыжки, что и даёт логарифм.

Способ через RMQ

Есть подход с константным временем запроса. Строим эйлеров обход дерева — последовательность вершин в порядке посещения, с возвратами:

1 2 4 2 5 7 5 8 5 2 1 3 6 3 1

Оказывается, LCA двух вершин — это вершина с минимальной глубиной на отрезке эйлерова обхода между их первыми вхождениями. Задача сводится к минимуму на отрезке (RMQ), который решается разреженной таблицей за O(1) на запрос после O(n log n) предподсчёта.

Подход даёт лучшую асимптотику запроса, но константа больше и памяти нужно вдвое-втрое больше. На практике двоичные подъёмы обычно предпочтительнее — код короче и понятнее.

Алгоритм Тарьяна для офлайн-запросов

Если все запросы известны заранее (офлайн), есть решение за почти линейное время через систему непересекающихся множеств. Один обход в глубину, во время которого отвечаем на запросы, — O(n + q·α(n)).

Применимо реже, потому что требует знать все пары заранее, но в олимпиадных задачах встречается.

Частые ошибки

Слишком маленький LOG. Если таблица подъёмов короче, чем нужно для высоты дерева, запросы дадут неверный ответ. Берите ceil(log2(n)) + 1.

Корень без обработки. У корня нет родителя. Общепринятый приём — считать родителем корня его самого: тогда прыжки вверх «упираются» в корень и не выходят за границы.

Проверка u == v после выравнивания. Если одна вершина является предком другой, второй этап не сработает — нужно вернуть ответ сразу после выравнивания глубин.

Рекурсивный обход на больших деревьях. На 10⁵ вершинах рекурсия в Python упадёт. В коде выше обход намеренно итеративный.

Цикл подъёма от малых k к большим. Даст неверный результат — жадность работает только в обратном порядке.

Что запомнить

• LCA — самый глубокий общий предок двух вершин.
• Главное применение: расстояние в дереве по формуле depth[u] + depth[v] − 2·depth[LCA].
• Двоичные подъёмы: таблица up[v][k] предков на 2^k вверх, запрос за O(log n).
• Сначала выравниваем глубины, потом поднимаем обе вершины максимальными безопасными прыжками.
• Второй цикл идёт от больших степеней двойки к меньшим — иначе не работает.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→