Эйлеров обход и LCA

Есть способ искать LCA, не поднимаясь по дереву вовсе. Он сводит задачу к минимуму на отрезке — а это уже решённая задача.

Эйлеров обход

Заменим мысленно каждое ребро дерева на два ориентированных, в обе стороны. У каждой вершины степени входа и выхода станут равны, значит, в таком графе есть эйлеров цикл — маршрут по всем рёбрам ровно по разу.

Строить его отдельно не нужно: обычный обход в глубину его и обходит. Достаточно выписывать вершину при входе и после возврата из каждого сына.

void dfs(int v, int p, int d) {
    pos[v] = order.size();
    order.push_back(v);
    depth.push_back(d);
    for (int u : g[v]) if (u != p) {
        dfs(u, v, d + 1);
        order.push_back(v);            // вернулись — выписываем снова
        depth.push_back(d);
    }
}

Длина массива — $2n - 1$: вершина выписывается один раз при входе и по разу на каждое ребро вверх.

Рядом храним глубины. pos[v] — какое-нибудь вхождение $v$; какое именно, неважно, поэтому запоминаем первое.

Сведение

Возьмём произвольные вхождения $u$ и $v$ в массив обхода. Вершина с наименьшей глубиной на отрезке между ними — это LCA.

Доказательство в двух шагах.

LCA на отрезке есть. Кусок маршрута из $u$ в $v$ обязан пройти по всем вершинам пути между ними в дереве, а путь в дереве единственный и проходит через LCA.

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

Значит, на отрезке лежит путь между $u$ и $v$, возможно, ещё какие-то поддеревья, свисающие с него вниз, и ничего выше. Минимум глубины достигается на LCA.

Реализация

int lca(int u, int v) {
    int l = pos[u], r = pos[v];
    if (l > r) swap(l, r);                    // про это забывают чаще всего
    return order[argmin_depth(l, r)];         // минимум на отрезке
}

Перестановка границ обязательна: запрос могли дать в любом порядке, а вхождение $v$ может оказаться левее вхождения $u$.

Проверено: на 20 000 деревьев, около 1,4 миллиона запросов, совпало с подъёмом по родителям и с обоими вариантами двоичных подъёмов.

Чем искать минимум

Дальше это уже не задача про деревья.

структура	предподсчёт	память	запрос
sparse table	$O(n \log n)$	$O(n \log n)$	$O(1)$
дерево отрезков	$O(n)$	$O(n)$	$O(\log n)$

Массив не меняется, поэтому дерево отрезков здесь избыточно — оно умеет обновления, которые не нужны. Берут его тогда, когда важна линейная память.

Sparse table даёт запрос за константу. При $10^7$ запросов разница с логарифмом — это разница между «зашло» и «не зашло».

Что ещё даёт эйлеров обход

Расстояние между вершинами — $\text{dep}_u + \text{dep}_v - 2\,\text{dep}_{\text{lca}}$, без отдельных структур.

Поддерево как отрезок. Есть родственный вариант обхода, где вершина выписывается только при входе; тогда поддерево занимает непрерывный кусок — про это в статье про времена входа и выхода. Не путайте эти два массива: у них разная длина и разное назначение.