LCA офлайн: алгоритм Тарьяна

Все предыдущие способы работают онлайн: запрос пришёл — ответили. Если запросы даны заранее, есть способ дешевле.

Что нужно знать

Алгоритм опирается на систему непересекающихся множеств (СНМ, DSU) — структуру, которая хранит разбиение элементов на группы и умеет две операции: узнать представителя группы элемента и объединить две группы. С эвристиками сжатия пути и объединения по рангу обе стоят $O(\alpha(n))$, где $\alpha$ — обратная функция Аккермана: величина, не превосходящая 4 для любых мыслимых $n$.

Ниже используется минимальный интерфейс: find(v) и «прилить группу $u$ к группе $v$».

Идея

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

Свойство групп: для всех вершин одной группы ответ на запрос с $v$ одинаков — это тот предок, за которым группа закреплена.

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

Группы не пересекаются — значит, их можно держать в СНМ.

Код

void dfs(int v, int p) {
    dsu[v] = v;
    anc[v] = v;                          // за группой v пока закреплена сама v
    for (int u : g[v]) if (u != p) {
        dfs(u, v);
        dsu[find(u)] = v;                // приливаем группу ребёнка
        anc[find(v)] = v;                // и переназначаем ответ на v
    }
    used[v] = true;
    for (auto [u, id] : queries[v])
        if (used[u]) answer[id] = anc[find(u)];
}

Порядок строк существенен. Пометка used[v] ставится после обхода детей, но до ответа на запросы: иначе запрос вида $(v, v)$ обработается неверно.

Строка anc[find(v)] = v нужна каждый раз после приливания: find мог поменять представителя, и ответ надо переназначить на новую голову.

Каждый запрос записывается в список обеих своих вершин; отвечаем на нём тогда, когда дошли до второй.

Проверено: 30 000 деревьев, 2 177 536 запросов — совпало с подъёмом по родителям.

Сложность

$O(n + q\,\alpha(n))$ — практически линия. Ни один онлайн-способ такого не даёт.

Плата — офлайн: все запросы должны быть известны до начала работы.

Какой способ когда

способ	предподсчёт	память	запрос	онлайн
подъём по родителям	$O(n)$	$O(n)$	$O(n)$	да
двоичные подъёмы	$O(n \log n)$	$O(n \log n)$	$O(\log n)$	да
прыжковые указатели	$O(n)$	$O(n)$	$O(\log n)$	да
эйлеров обход + дерево отрезков	$O(n)$	$O(n)$	$O(\log n)$	да
эйлеров обход + sparse table	$O(n \log n)$	$O(n \log n)$	$O(1)$	да
Тарьян	$O(n)$	$O(n + q)$	$\alpha(n)$	нет

Практическое правило:

• по умолчанию — двоичные подъёмы: пишутся быстрее всего и попутно дают функции на пути и Level Ancestor;
• очень много запросов ($10^7$ и выше) — эйлеров обход с sparse table;
• жёсткий лимит памяти — прыжковые указатели или эйлеров обход с деревом отрезков;
• запросы даны заранее и их очень много — Тарьян.

В контестах по этой теме ограничения обычно подбирают так, чтобы разные задачи требовали разных способов. Поэтому знать полезно все.