18.1 Поиск предков¶

Этот раздел посвящён одной из базовых задач на деревья: как быстро находить предка вершины на несколько уровней выше.

Идея задачи¶

Пусть дерево корневое, то есть у него выбрана корневая вершина. Для каждой вершины, кроме корня, известен её родитель.

k-й предок вершины x — это вершина, в которую мы попадём, если поднимемся от x вверх по дереву ровно на k рёбер.

Обозначим это так:

ancestor(x, k) — k-й предок вершины x.

Если такого предка не существует, будем считать ответом 0 или -1 — в зависимости от выбранного соглашения в программе.

Пример¶

Рассмотрим дерево:

1

/| 2 4 5 /
6 7 / 8

Для него:

• ancestor(2, 1) = 1
• ancestor(6, 1) = 2
• ancestor(6, 2) = 1
• ancestor(8, 1) = 7
• ancestor(8, 2) = 4
• ancestor(8, 3) = 1
• ancestor(8, 4) = 0, потому что выше корня уже ничего нет

Наивное решение¶

Самый простой способ — подниматься вверх по одному ребру k раз.

То есть:

1. берём вершину x
2. заменяем её на родителя
3. повторяем это k раз

Такой способ работает за O(k) на один запрос.

Почему этого может не хватить¶

Если дерево — это длинная цепочка из n вершин, то k может быть почти равно n. Тогда один запрос может работать очень долго.

Если запросов много, например до 2 * 10^5, такой подход становится слишком медленным.

Главное ускорение¶

Вместо того чтобы хранить только непосредственного родителя, будем хранить предков на расстояниях:

• 2^0 = 1
• 2^1 = 2
• 2^2 = 4
• 2^3 = 8
• и так далее

То есть для каждой вершины v заранее посчитаем:

• её предка на 1 уровень выше
• её предка на 2 уровня выше
• её предка на 4 уровня выше
• её предка на 8 уровней выше
• ...

Этот приём называется binary lifting — двоичный подъём.

Почему это работает¶

Любое число k можно разложить по степеням двойки.

Например:

• 13 = 8 + 4 + 1
• 10 = 8 + 2
• 19 = 16 + 2 + 1

Значит, чтобы подняться на 13 уровней вверх, можно:

1. сначала подняться на 8
2. потом ещё на 4
3. потом ещё на 1

Итого получится 13.

Это похоже на быстрые прыжки вместо движения по одному шагу.

Таблица предков¶

Пусть up[v][j] — это предок вершины v на расстоянии 2^j вверх.

Тогда:

• up[v][0] — обычный родитель
• up[v][1] — предок на 2 уровня вверх
• up[v][2] — предок на 4 уровня вверх
• up[v][3] — предок на 8 уровней вверх

Переход¶

Если мы уже знаем предка на 2^(j-1), то предка на 2^j можно получить так:

up[v][j] = up[ up[v][j-1] ][j-1]

Смысл очень простой:

• сначала поднимаемся на 2^(j-1)
• из полученной вершины поднимаемся ещё на 2^(j-1)
• вместе получаем 2^j

Небольшой пример таблицы¶

Для дерева выше часть таблицы может выглядеть так:

Например:

• up[8][0] = 7
• up[8][1] = 4, потому что это предок на 2 уровня вверх
• up[8][2] = 0, потому что предка на 4 уровня уже нет

Как отвечать на запрос¶

Чтобы найти ancestor(x, k), смотрим на двоичную запись числа k.

Если в записи есть бит j, значит надо сделать прыжок на 2^j вверх.

Пример: найти ancestor(8, 3)¶

Число 3 в двоичной записи — это 11, то есть:

3 = 2 + 1

Значит:

1. прыгаем из 8 на 1 вверх → попадаем в 7
2. прыгаем из 7 на 2 вверх → попадаем в 1

Ответ: 1.

Пример: найти ancestor(8, 5)¶

5 = 4 + 1

1. прыгаем на 1 вверх: 8 -> 7
2. прыгаем на 4 вверх: у 7 такого предка уже нет

Ответ: 0.

Схема идеи¶

graph TD
    A[Запрос ancestor(x, k)] --> B[Разложить k по битам]
    B --> C[Если j-й бит включён, сделать прыжок на 2^j]
    C --> D[Использовать таблицу up[v][j]]
    D --> E[Получить ответ за O(log k)]

Предобработка¶

Обычно таблицу up строят после DFS или BFS от корня.

Нам нужны:

• parent[v] — родитель вершины
• depth[v] — глубина вершины, иногда это удобно для дополнительных задач
• up[v][j] — таблица двоичных прыжков

Как выбрать количество столбцов¶

Если n <= 2 * 10^5, то достаточно около 18–20 столбцов, потому что:

• 2^17 = 131072
• 2^18 = 262144

Обычно берут:

LOG = 20 или LOG = 21

Для общего случая удобно брать:

LOG = ceil(log2(n)) + 1

Реализация на C++¶

Ниже — базовая реализация для дерева с корнем в вершине 1.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    int LOG = 1;
    while ((1 << LOG) <= n) LOG++;

    vector<vector<int>> g(n + 1);
    for (int v = 2; v <= n; v++) {
        int p;
        cin >> p;
        g[p].push_back(v);
        g[v].push_back(p);
    }

    vector<int> depth(n + 1, 0);
    vector<vector<int>> up(n + 1, vector<int>(LOG, 0));

    function<void(int,int)> dfs = [&](int v, int p) {
        up[v][0] = p;
        for (int j = 1; j < LOG; j++) {
            up[v][j] = up[up[v][j - 1]][j - 1];
        }

        for (int to : g[v]) {
            if (to == p) continue;
            depth[to] = depth[v] + 1;
            dfs(to, v);
        }
    };

    dfs(1, 0);

    auto ancestor = [&](int x, int k) {
        for (int j = 0; j < LOG; j++) {
            if (k & (1 << j)) {
                x = up[x][j];
                if (x == 0) break;
            }
        }
        return x;
    };

    while (q--) {
        int x, k;
        cin >> x >> k;
        cout << ancestor(x, k) << '\n';
    }

    return 0;
}

Как устроен код¶

1. Вход¶

Мы читаем дерево в формате:

• есть n вершин
• для каждой вершины от 2 до n задан её родитель

Это популярный формат в задачах.

2. DFS¶

Во время обхода:

• запоминаем родителя
• сразу заполняем строку up[v][j]
• при желании можем хранить глубину

3. Ответ на запрос¶

Если в числе k установлен бит j, делаем прыжок на 2^j вверх.

Именно поэтому время одного запроса — O(log n).

Более школьная версия функции запроса¶

Иногда удобно вынести поиск предка в отдельную функцию.

int get_ancestor(int x, int k, const vector<vector<int>>& up) {
    int LOG = (int)up[0].size();
    for (int j = 0; j < LOG; j++) {
        if (k & (1 << j)) {
            x = up[x][j];
            if (x == 0) return 0;
        }
    }
    return x;
}

Пример¶

Пусть родители заданы так:

• parent[2] = 1
• parent[3] = 1
• parent[4] = 2
• parent[5] = 2
• parent[6] = 4

Тогда дерево такое:

graph TD
    1 --> 2
    1 --> 3
    2 --> 4
    2 --> 5
    4 --> 6

Запросы:

• ancestor(6, 1) = 4
• ancestor(6, 2) = 2
• ancestor(6, 3) = 1
• ancestor(6, 4) = 0
• ancestor(5, 2) = 1

Альтернативный способ построения¶

Если родители уже даны во входе, то таблицу можно построить даже без DFS.

Сначала задаём:

• up[v][0] = parent[v]

Потом для всех j:

up[v][j] = up[up[v][j-1]][j-1]

Это особенно удобно, когда дерево уже задано как массив родителей, а глубины не нужны.

Код такого варианта¶

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    int LOG = 1;
    while ((1 << LOG) <= n) LOG++;

    vector<vector<int>> up(n + 1, vector<int>(LOG, 0));

    for (int v = 2; v <= n; v++) {
        cin >> up[v][0];
    }

    for (int j = 1; j < LOG; j++) {
        for (int v = 1; v <= n; v++) {
            up[v][j] = up[up[v][j - 1]][j - 1];
        }
    }

    while (q--) {
        int x, k;
        cin >> x >> k;
        for (int j = 0; j < LOG; j++) {
            if (k & (1 << j)) {
                x = up[x][j];
                if (x == 0) break;
            }
        }
        cout << x << '\n';
    }

    return 0;
}

Оценка сложности¶

Предобработка¶

Для каждой вершины мы считаем LOG значений.

Итого:

• время: O(n log n)
• память: O(n log n)

Один запрос¶

Мы перебираем все биты числа k.

Итого:

• время: O(log k)

Так как обычно k <= n, чаще всего пишут просто O(log n).

Где это применяется¶

Задача про k-го предка важна сама по себе, но ещё важнее то, что это база для других тем:

• LCA — наименьший общий предок
• запросы на пути в дереве
• прыжки по функциональному графу
• обработка большого числа запросов к дереву

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

Типичные ошибки¶

1. Слишком маленький LOG¶

Если взять слишком мало столбцов, большие прыжки не будут работать.

2. Неправильное значение для отсутствующего предка¶

Нужно заранее договориться, что означает «предка нет»:

• 0, если вершины нумеруются с 1
• -1, если хотите другой стиль

Но это соглашение должно быть одинаковым во всей программе.

3. Ошибка в формуле перехода¶

Правильная формула:

up[v][j] = up[up[v][j-1]][j-1]

Иногда по невнимательности пишут не тот индекс и таблица ломается.

4. Перепутан корень¶

Если дерево корневое, нужно чётко понимать, где находится корень. Именно от него строятся родители и глубины.

Что полезно запомнить¶

1. Наивный подъём по одному ребру слишком медленный.
2. Нужно хранить предков на расстояниях 1, 2, 4, 8, ....
3. Любой запрос раскладывается по битам числа k.
4. Предобработка занимает O(n log n).
5. Каждый запрос обрабатывается за O(log n).

Вывод¶

Поиск k-го предка — это одна из самых удобных задач для применения двоичного подъёма.

Мы заранее строим таблицу прыжков по степеням двойки, а затем любой большой подъём вверх заменяем на несколько быстрых прыжков. За счёт этого задача, которая наивно решалась бы за O(k), начинает работать за O(log n) на запрос.