Level Ancestor и лестницы

Задача Level Ancestor: дана вершина $v$ и число $k$, найти предка $v$, стоящего ровно на $k$ рёбер выше.

Двоичные подъёмы решают её сразу: раскладываем $k$ по битам и делаем прыжки. $O(\log n)$ на запрос. Но можно за $O(1)$.

Разбиение на длиннейшие пути

Определим глубину вершины как расстояние до самого далёкого листа в её поддереве.

Разобьём дерево на вертикальные пути: начиная из корня, продолжаем путь в того сына, у которого глубина наибольшая. Остальные сыновья начинают свои пути.

void build(int v, int p, int id) {
    pathId[v] = id;
    pathPos[v] = paths[id].size();
    paths[id].push_back(v);
    int best = -1;
    for (int u : g[v]) if (u != p)
        if (best == -1 || deepest[u] > deepest[best]) best = u;
    if (best != -1) build(best, v, id);
    for (int u : g[v]) if (u != p && u != best) {
        paths.push_back({});
        build(u, v, paths.size() - 1);
    }
}

Если бы ответ всегда лежал на том же пути, что и $v$, запрос сводился бы к paths[pathId[v]][pathPos[v] - k] — обращение в массив, $O(1)$.

Но путь может кончиться раньше, чем мы поднимемся на $k$. Тогда так не выйдет.

Лестницы

Приём: удлиним каждый путь вверх вдвое. Если в пути было $\ell$ вершин, допишем в начало ещё $\ell$ вершин-предков (или меньше, если упёрлись в корень).

Эти дописанные вершины принадлежат другим путям — они дублируются. Памяти уходит вдвое больше, зато появляется запас сверху. Такое удлинённое разбиение называется лестничной декомпозицией.

Запрос за константу

Пусть $2^\ell$ — наибольшая степень двойки, не превосходящая $k$. Сделаем один двоичный прыжок на $2^\ell$ и попадём в вершину $w$. Осталось подняться на $k - 2^\ell < 2^\ell$.

Утверждение: этот остаток гарантированно лежит внутри лестницы вершины $w$.

Почему. Из $w$ вниз идёт путь длины хотя бы $2^\ell$ — по нему мы только что пришли из $v$. Значит, глубина $w$ не меньше $2^\ell$, и длиннейший путь через $w$ имеет длину хотя бы $2^\ell$. Удлинив его вдвое, мы получили запас сверху тоже не меньше $2^\ell$. А подняться осталось меньше, чем на $2^\ell$.

int levelAncestor(int v, int k) {
    if (k == 0) return v;
    int l = __lg(k);
    int w = up[l][v];                       // единственный двоичный прыжок
    int rest = k - (1 << l);
    return ladders[pathId[w]][ladderPos[w] - rest];
}

Предподсчёт $O(n \log n)$ — из-за таблицы двоичных подъёмов. Запрос $O(1)$.

Проверено: 20 000 деревьев, 765 534 запроса — ответы совпали с подъёмом по родителям, и лестницы хватало во всех случаях. Это как раз тот шаг рассуждения, который проще проверить, чем перепроверить на бумаге.

Родственная декомпозиция

Если продолжать путь не в самого «глубокого» сына, а в сына с наибольшим размером поддерева, получится тяжёло-лёгкая декомпозиция (HLD). У неё другое свойство: путь между любыми двумя вершинами пересекает не более $O(\log n)$ путей разбиения. Она нужна для запросов на путях с изменениями, и это отдельная тема.

Разница в одном слове — «глубокий» против «большого», — а применения разные.