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

Если ты знаешь определение LCA, умеешь считать расстояние через глубины и понимаешь, почему наивный подъём стоит O(глубины), листай до «Теперь сам».

Как думаешь, где ветки разошлись

Представь историю версий проекта: дерево коммитов, каждый знает своего родителя. Прежде чем читать дальше, ответь: как найти коммит, в котором разошлись две ветки? И сколько шагов это займёт, если ветки разошлись тысячу коммитов назад, а история длиной в миллион?

На что это похоже

Генеалогическое древо и вопрос «кем эти двое друг другу приходятся». Способ, которым это делают люди: поднимаемся от обоих по поколениям, пока не упрёмся в общего предка. Если один потомок младше, сперва подтягиваем его на тот же уровень поколений, а потом идём вверх синхронно. Общий предок, найденный первым, - самый близкий, а не какой-нибудь прапрадед.

Механизм: глубина, родитель, подъём

parent = [0] * V
depth = [0] * V
tin = [0] * V
tout = [0] * V
timer = 0

def dfs(v, p):
    global timer
    parent[v] = p
    tin[v] = timer; timer += 1
    for u in adj[v]:            # обычный список смежности, как во всём разделе
        if u != p:              # родителя пропускаем - иначе уйдём обратно
            depth[u] = depth[v] + 1
            dfs(u, v)
    tout[v] = timer; timer += 1

# У КОРНЯ родителем считаем его самого - это соглашение понадобится в следующем
# уроке (в таблице подъёмов -1 читался бы как индекс последнего элемента).
depth[root] = 0
dfs(root, root)

def is_ancestor(u, v):                 # из главы про обход: O(1)
    return tin[u] <= tin[v] and tout[v] <= tout[u]

def lca_naive(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

Две формулы, ради которых LCA чаще всего и считают:

расстояние в дереве:  dist(u, v) = depth[u] + depth[v] − 2·depth[ LCA(u, v) ]
лежит ли v в поддереве u:  tin[u] <= tin[v] и tout[v] <= tout[u]     ← O(1)

Первая работает потому, что путь между вершинами в дереве единственный и проходит ровно через их наименьшего общего предка: поднимаемся из u до него (depth[u] − depth[LCA] шагов) и спускаемся к v (ещё depth[v] − depth[LCA]).

Правило

LCA(u, v) - самая глубокая вершина, являющаяся предком и u, и v (вершина считается предком самой себя). Наивный алгоритм: подтянуть более глубокую вершину до уровня второй по родительским ссылкам, затем поднимать обе синхронно до совпадения - O(глубины), в худшем случае O(V). Расстояние в дереве: dist(u, v) = depth[u] + depth[v] − 2·depth[LCA(u, v)]. Проверка «является ли u предком v» - O(1) через времена входа и выхода.

Разбор: считаем LCA и расстояние руками

Дерево: корень r; дети r - p и c; дети p - a и b; ребёнок a - u; ребёнок c - d. Глубины: r = 0, p = c = 1, a = b = d = 2, u = 3.

LCA(u, b). Глубины 3 и 2 - подтягиваем u: u → a, теперь обе на глубине 2 (a и b). Не совпали - поднимаем обе: a → p, b → p. Совпали: LCA = p. Расстояние: depth[u] + depth[b] − 2·depth[p] = 3 + 2 − 2·1 = 3. Проверим по картинке: u → a → p → b - три ребра ✓.

LCA(u, d). Глубины 3 и 2 - подтягиваем u до a. Поднимаем обе: a → p, d → c. Не совпали. Ещё раз: p → r, c → r. Совпали: LCA = r. Расстояние: 3 + 2 − 2·0 = 5: u → a → p → r → c → d - пять рёбер ✓.

LCA(a, u). Здесь важный частный случай: a - предок u. Подтягиваем u с глубины 3 до глубины 2 - получаем a, и цикл синхронного подъёма не делает ни одного шага, потому что вершины уже совпали. LCA = a - и это правильный ответ: вершина считается предком самой себя.

Разбор: почему наивный способ иногда невыносим

Цена одного запроса - O(глубины). В сбалансированном дереве глубина log V, и миллион запросов к дереву из миллиона вершин обойдётся в 20·10⁶ шагов - терпимо. Но дерево не обязано быть сбалансированным: история версий, дерево каталогов, цепочка комментариев, дерево разбораРазбирается в разделе 21, глава «Контекстно-свободные языки и магазинные автоматы»: Грамматика: правила, которые порождают язык, и дерево разбора длинного выражения легко вытягиваются в почти линейную цепочку. Тогда глубина V, и миллион запросов - это 10¹² операций, то есть часы.

Отсюда постановка задачи, которой занят остаток главы: сделать ПРЕДПОДСЧЁТ, после которого каждый запрос стоит O(log V) или даже O(1). Ключевое наблюдение, ведущее к решению: наивный подъём шагает по одному родителю за раз, а это то же самое, что искать число, прибавляя единицу. Если бы мы умели прыгать сразу на 1, 2, 4, 8, ... предков, любой подъём собирался бы из log V прыжков - ровно как любое число собирается из степеней двойки. Это и есть двоичные подъёмы из следующего урока.

Что ломается без этого

Первое: забыть подтянуть вершины к одной глубине и начать поднимать сразу обе - они разминутся и никогда не совпадут (либо совпадут случайно, дав неверный ответ). Второе: считать, что вершина не является предком самой себя - тогда LCA(a, u) для предка и потомка вернёт родителя a, и все расстояния сдвинутся. Третье: применять LCA к графу, который не дерево, - понятие определено для деревьев (и для ДАГов оно другое, там общих предков может быть несколько несравнимых). Четвёртое: хранить глубину как число рёбер в одном месте и как число вершин в другом - формула расстояния сразу начнёт врать на единицу; глубина корня должна быть нулём. Пятое: рекурсивный обход для построения parent и depth на цепочке из миллиона вершин - привет переполнение стека, о котором была отдельная речь.

Зачем это в работе

LCA - это «где разошлись» и «как далеко друг от друга». Системы контроля версий ищут базу слияния двух веток - буквально LCA в дереве коммитов (в общем случае это ДАГ, и там сложнее, но идея та же). Файловые системы и права доступа: общий родительский каталог двух путей. Иерархии организаций и категорий: ближайшая общая категория двух товаров, общий руководитель двух сотрудников. В вычислительной геометрии и биоинформатике LCA в суффиксных деревьяхРазбирается в разделе 17, глава «Суффиксный массив, LCP и суффиксное дерево»: Суффиксное дерево: сжатый бор всех суффиксов даёт длину наибольшего общего префикса двух подстрок. Плюс целое семейство задач на деревьях, где ответ считается как «сумма по пути» и раскладывается через предка: f(u, v) = f(корень, u) + f(корень, v) − 2·f(корень, LCA) - тот же приём, что и с расстоянием.

Теперь сам

Дерево: корень 1; дети 1 - вершины 2 и 3; дети 2 - вершины 4 и 5; ребёнок 4 - вершина 6; ребёнок 3 - вершина 7. Найди LCA(6, 5), LCA(6, 7) и расстояния между этими парами.