Двоичные подъёмы: прыжки на 1, 2, 4, 8 предков

Если ты умеешь строить таблицу up[v][k], поднимать вершину на произвольное число шагов по битам и находить LCA прыжками «пока не совпали», листай до «Теперь сам».

Как думаешь, почему степени двойки

Наивный подъём делает шаги по одному. Прежде чем читать дальше, вспомни, как из степеней двойки собирается любое число (13 = 8 + 4 + 1), и подумай: если бы у каждой вершины была ссылка не только на родителя, но и на предка через 2, 4, 8 шагов - за сколько прыжков можно было бы подняться на 13 уровней? А на миллион?

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

Экспресс-лифты в небоскрёбе. Обычный лифт останавливается на каждом этаже - чтобы подняться на тысячу этажей, нужна тысяча остановок. Экспрессы ходят через 2, 4, 8, 16 этажей: собрав маршрут из них по двоичной записи числа, поднимаешься за десяток пересадок. Ничего нового не построено - просто заранее проложены маршруты длиной в степень двойки.

Механизм: таблица предков и два применения

LOG = 0
while (1 << LOG) < V:          # 2^LOG >= V: столько уровней хватает на любой подъём
    LOG += 1                   # таблица хранит k = 0, 1, ..., LOG

up = [[0] * (LOG + 1) for _ in range(V)]

# up[v][0] - родитель; у корня родителем считаем его самого
for v in range(V):
    up[v][0] = parent[v]

for k in range(1, LOG + 1):
    for v in range(V):
        up[v][k] = up[ up[v][k - 1] ][k - 1]      # два прыжка по 2^(k−1)

Подъём на произвольное число шагов - по двоичной записи:

def lift(v, steps):
    k = 0
    while steps:
        if steps & 1:
            v = up[v][k]
        steps >>= 1
        k += 1
    return v

LCA двумя фазами:

def lca(u, v):
    if depth[u] < depth[v]:
        u, v = v, u
    u = lift(u, depth[u] - depth[v])        # фаза 1: выровняли глубины
    if u == v:
        return u                            # один оказался предком другого
    for k in range(LOG, -1, -1):            # фаза 2: прыгаем от больших к меньшим
        if up[u][k] != up[v][k]:            # пока предки РАЗНЫЕ - прыгаем
            u = up[u][k]
            v = up[v][k]
    return up[u][0]                         # остановились под ответом

Вторая фаза - самая неочевидная часть, и её стоит проговорить: мы поднимаемся настолько, насколько можно, НЕ поднявшись выше ответа. Если предки на 2^k шагов различаются, значит ответ ещё выше - прыгаем смело. Если совпадают, прыжок мог бы перелететь ответ - пропускаем. После перебора всех k от большего к меньшему обе вершины стоят ровно под наименьшим общим предком, и ответ - их родитель.

Правило

Таблица up[v][k] - предок вершины v на 2^k шагов вверх; строится как up[v][k] = up[up[v][k−1]][k−1] за O(V·log V) времени и памяти (родителем корня считают его самого). Подъём на произвольное число шагов - по двоичной записи числа, O(log V). LCA: выровнять глубины подъёмом; если вершины совпали - одна была предком другой; иначе прыгать обеими от больших k к меньшим, пока предки РАЗЛИЧАЮТСЯ, и вернуть up[u][0]. Запрос - O(log V).

Разбор: строим таблицу на цепочке

Дерево-цепочка: 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 (нулевая вершина - корень, каждая следующая её потомок). LOG = 3, потому что 2³ = 8 >= 8.

k=0 (родители):     up[v][0] = v−1, у корня up[0][0] = 0
                    up = [0, 0, 1, 2, 3, 4, 5, 6]
k=1 (через 2):      up[v][1] = up[up[v][0]][0]
                    up[7][1] = up[6][0] = 5;  up[3][1] = up[2][0] = 1;  up[1][1] = up[0][0] = 0
                    up = [0, 0, 0, 1, 2, 3, 4, 5]
k=2 (через 4):      up[v][2] = up[up[v][1]][1]
                    up[7][2] = up[5][1] = 3;  up[6][2] = up[4][1] = 2
                    up = [0, 0, 0, 0, 0, 1, 2, 3]
k=3 (через 8):      все упираются в корень → up = [0, 0, 0, 0, 0, 0, 0, 0]

Проверим подъём: поднять вершину 7 на 5 шагов. 5 = 101₂, значит прыжки k=0 и k=2: up[7][0] = 6, затем up[6][2] = 2. Ответ - вершина 2, и это верно: от семёрки пять шагов вверх это 7→6→5→4→3→2. Пять шагов превратились в два прыжка.

Разбор: почему вторая фаза не перелетает ответ

Разберём, почему условие «прыгаем, пока предки РАЗЛИЧАЮТСЯ» корректно.

Пусть L = LCA(u, v), и обе вершины уже на одной глубине, причём u != v. Обозначим h - сколько шагов вверх от u до L (столько же и от v, глубины равны). Наша цель - подняться ровно на h − 1 шаг, чтобы встать под ответом.

Смотрим на прыжок длиной 2^k. Если up[u][k] == up[v][k], то предок на 2^k шагов у обеих один и тот же, а значит он является общим предком, то есть 2^k >= h - прыжок перелетел бы (или попал точно в) L; такой прыжок пропускаем. Если up[u][k] != up[v][k], предки разные, значит 2^k < h - прыгнуть безопасно, до ответа ещё далеко.

Перебирая k от большего к меньшему и прыгая, когда можно, мы собираем число h − 1 из степеней двойки - в точности как при обычном разложении числа в двоичную запись жадным алгоритмом. В конце u и v стоят на расстоянии одного шага от L, и ответ - up[u][0].

Заметь, зачем нужна проверка u == v после первой фазы: если одна вершина была предком другой, то после выравнивания глубин они совпадут, а вторая фаза с её «пока различаются» не сделает ни одного прыжка и вернёт up[u][0] - родителя ответа. То есть без этой проверки ответ был бы на один уровень выше нужного. Это самая частая ошибка в реализациях LCA.

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

Первое: забыть проверку «одна вершина - предок другой» после выравнивания. Ответ получается на уровень выше, и обнаруживается это только на конкретных парах. Второе: у корня в up[корень][0] поставить -1 вместо самого корня - тогда индексация по -1 начнёт читать конец массива (в Python молча), и таблица испортится. Третье: во второй фазе идти от МАЛЕНЬКИХ k к большим - так алгоритм перелетит ответ; порядок обязателен убывающий. Четвёртое: взять LOG меньше нужного - на глубоких деревьях подъём не достанет до корня, и ответы станут неверными; LOG считают по V, а не по глазомеру. Пятое: строить таблицу в неправильном порядке - при вычислении слоя k слой k−1 должен быть готов ЦЕЛИКОМ для всех вершин, поэтому внешний цикл идёт по k, а не по вершинам.

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

Двоичные подъёмы - это не только LCA. Тем же приёмом отвечают на вопросы «какой предок вершины на k-м уровне выше», «максимум на пути от вершины к предку» (храним рядом с up[v][k] максимум на этом отрезке пути - и получаем максимум на пути за O(log V)), «первая вершина вверх, удовлетворяющая условию». В играх и симуляциях так ищут состояние через k шагов в функциональном графе («переход по указателю k раз»), в базах данных - предка в иерархии на заданном уровне. А сама схема «предподсчитать степени двойки, а потом собирать ответ по битам» встречается и вне деревьев: разреженная таблица из следующего урока устроена ровно так же, только по массиву. Это общий приём: дорогой повторяющийся путь разбивают на куски длиной в степень двойки и предподсчитывают их.

Теперь сам

Дерево: корень 0; 1 и 2 - дети нуля; 3 - ребёнок единицы; 4 - ребёнок тройки; 5 - ребёнок двойки. Построй up[v][0] и up[v][1], затем найди LCA(4, 5) по алгоритму.