18.3 Наименьший общий предок¶

Что такое LCA¶

Наименьший общий предок двух вершин дерева a и b — это самая глубокая вершина, в поддереве которой лежат обе вершины.

Обычно используют английское сокращение LCA — Lowest Common Ancestor.

Если дерево укоренено, то задача формулируется очень естественно: нужно найти самую нижнюю общую вершину на пути от корня к a и от корня к b.

Небольшой пример¶

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

graph TD
    n1[1] --> n2[2]
    n1 --> n3[3]
    n2 --> n4[4]
    n2 --> n5[5]
    n3 --> n6[6]
    n6 --> n7[7]
    n6 --> n8[8]

• LCA(4, 5) = 2
• LCA(7, 8) = 6
• LCA(5, 8) = 1
• LCA(2, 5) = 2, потому что вершина может быть предком самой себя

Зачем вообще нужен LCA¶

Эта задача встречается очень часто:

• найти расстояние между двумя вершинами;
• отвечать на запросы по путям в дереве;
• проверять отношения предок–потомок;
• решать задачи на маршруты, запросы и структуру дерева.

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

Базовая идея¶

Если выписать путь от корня до a и путь от корня до b, то LCA — это последняя общая вершина в этих двух путях.

Например:

• путь к 5: 1 -> 2 -> 5
• путь к 8: 1 -> 3 -> 6 -> 8

Последняя общая вершина — 1, значит LCA(5, 8) = 1.

Но хранить и сравнивать пути для каждого запроса невыгодно. Поэтому нужны более быстрые методы.

Подход 1. Подъём по предкам¶

Это самый понятный способ думать о LCA.

Идея¶

Пусть глубины вершин равны depth[a] и depth[b].

1. Сначала поднимем более глубокую вершину вверх, пока обе вершины не окажутся на одной глубине.
2. Затем будем поднимать их одновременно.
3. Когда вершины совпадут, мы и найдём LCA.

Пример¶

Пусть нужно найти LCA(7, 8).

• обе вершины имеют одинаковую глубину;

• поднимаем обе:

• 7 -> 6

• 8 -> 6
• встретились в 6, значит ответ 6

А если искать LCA(5, 8):

• 8 глубже, чем 5, сначала поднимаем 8 до той же глубины;
• потом поднимаем обе вершины;
• в итоге они встретятся в 1.

Наивная реализация¶

Если хранить только непосредственного родителя parent[v], то один запрос может занять O(n) в худшем случае, например в вырожденном дереве-цепочке.

Это уже работает, но для большого числа запросов медленно.

Подход 2. Двоичный подъём¶

Это один из самых популярных способов решать LCA в олимпиадном программировании.

Идея¶

Для каждой вершины будем хранить не только родителя, но и предков на расстояниях:

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

Обозначим:

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

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

Как заполняется таблица¶

Используется формула:

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

То есть предок на 2^j — это предок на 2^(j-1) от предка на 2^(j-1).

Алгоритм запроса¶

Чтобы найти LCA(a, b):

1. Если a глубже, чем b, поднимаем a вверх до глубины b.
2. Если после этого a == b, ответ найден.
3. Идём по степеням двойки от больших к меньшим. Если up[a][j] != up[b][j], поднимаем обе вершины на 2^j.
4. После этого вершины станут детьми LCA, и ответом будет их общий родитель.

Сложность¶

• Предобработка: O(n log n)
• Один запрос: O(log n)
• Память: O(n log n)

Это отличный вариант, если запросов много.

Подход 3. Эйлеров обход + RMQ¶

Именно эту идею кратко приводит книга: задача LCA сводится к поиску минимума на отрезке.

Главная мысль¶

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

Тогда:

• вершина с k детьми появится k + 1 раз;
• длина массива обхода будет 2n - 1.

Для каждой позиции в массиве храним:

• номер вершины;
• её глубину.

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

Возьмём две вершины a и b.

Рассмотрим их первые появления в массиве Эйлерова обхода. Если посмотреть на отрезок между этими появлениями, то вершина с минимальной глубиной на этом отрезке и будет LCA.

Интуитивно это так:

• обход сначала спускается к одной вершине;
• потом поднимается до общего предка;
• затем спускается ко второй вершине;
• самая верхняя точка между ними — и есть наименьший общий предок.

Пример массива обхода¶

Для дерева

graph TD
    n1[1] --> n2[2]
    n1 --> n3[3]
    n2 --> n5[5]
    n2 --> n6[6]
    n6 --> n8[8]
    n3 --> n4[4]
    n4 --> n7[7]

один из возможных Эйлеровых обходов:

• вершины: 1, 2, 5, 2, 6, 8, 6, 2, 1, 3, 1, 4, 7, 4, 1
• глубины: 1, 2, 3, 2, 3, 4, 3, 2, 1, 2, 1, 2, 3, 2, 1

Если искать LCA(5, 8):

• первое появление 5 — позиция 2;
• первое появление 8 — позиция 5;
• на отрезке 2..5 минимальная глубина равна 2 и достигается в вершине 2.

Значит, LCA(5, 8) = 2.

Во что сводится задача¶

После построения Эйлерова обхода LCA сводится к запросу:

• найти минимум глубины на отрезке.

Это уже обычный RMQ (range minimum query).

Если использовать sparse table:

• предобработка: O(n log n)
• запрос LCA: O(1)

Когда этот метод особенно хорош¶

Он очень удобен, когда:

• нужно очень много запросов;
• у нас уже есть структура для RMQ;
• хочется получить O(1) на запрос после предобработки.

Как найти расстояние между вершинами через LCA¶

Если известен c = LCA(a, b), то расстояние между вершинами равно

depth[a] + depth[b] - 2 * depth[c]

Почему формула верна¶

Путь от a к b можно разбить на две части:

• от a вверх до c;
• от c вниз до b.

Количество рёбер в первой части равно depth[a] - depth[c], во второй — depth[b] - depth[c].

Сумма:

(depth[a] - depth[c]) + (depth[b] - depth[c]) = depth[a] + depth[b] - 2 * depth[c]

Пример¶

Пусть:

• depth[5] = 3
• depth[8] = 4
• LCA(5, 8) = 2
• depth[2] = 2

Тогда расстояние:

3 + 4 - 2 * 2 = 3

И действительно, путь такой: 5 -> 2 -> 6 -> 8.

Какой метод выбрать¶

1. Подъём по родителям¶

Подходит, если:

• запросов мало;
• хочется очень простое решение;
• ограничения небольшие.

2. Двоичный подъём¶

Подходит почти всегда.

Плюсы:

• легко объяснить;
• легко реализовать;
• хорошо работает на практике;
• кроме LCA, можно удобно поднимать вершину на k уровней вверх.

3. Эйлеров обход + RMQ¶

Подходит, если:

• запросов очень много;
• хочется O(1) на запрос;
• вы уверенно владеете sparse table.

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

Реализация LCA через двоичный подъём на C++¶

Ниже — полноценная реализация. Она поддерживает:

• построение по дереву;
• поиск LCA;
• расстояние между вершинами.

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

  const int MAXN = 200005;
  const int LOG = 20;

  vector<int> g[MAXN];
  int up[MAXN][LOG];
  int depthv[MAXN];

  void 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;
        depthv[to] = depthv[v] + 1;
        dfs(to, v);
    }

  }

  int lift(int v, int k) {
  for (int j = 0; j < LOG; j++) {
  if (k & (1 << j)) {
  v = up[v][j];
  }
  }
  return v;
  }

  int lca(int a, int b) {
  if (depthv[a] < depthv[b]) swap(a, b);
    a = lift(a, depthv[a] - depthv[b]);

    if (a == b) return a;

    for (int j = LOG - 1; j >= 0; j--) {
        if (up[a][j] != up[b][j]) {
            a = up[a][j];
            b = up[b][j];
        }
    }

    return up[a][0];

  }

  int dist(int a, int b) {
  int c = lca(a, b);
  return depthv[a] + depthv[b] - 2 * depthv[c];
  }

  int main() {
  int n;
  cin >> n;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    depthv[1] = 0;
    dfs(1, 1);

    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << " " << dist(a, b) << '\n';
    }

  }

Что делает эта программа¶

• Читает дерево из n вершин.
• Считает, что корень — вершина 1.
• Строит таблицу предков up.

• Для каждого запроса выводит:

• LCA двух вершин;

• расстояние между ними.

Пример входа¶

8
1 2
1 3
2 4
2 5
3 6
6 7
6 8
4
4 5
7 8
5 8
2 5

Пример выхода¶

2 2
6 2
1 5
2 1

Реализация LCA через Эйлеров обход и sparse table на C++¶

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

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

const int MAXN = 200005;
const int MAXM = 400005;
const int LOG = 20;

vector<int> g[MAXN];
int depthv[MAXN];
int firstPos[MAXN];
vector<int> euler;
vector<int> eulerDepth;
int st[MAXM][LOG];
int lg[MAXM];

void dfs(int v, int p, int d) {
    depthv[v] = d;
    firstPos[v] = (int)euler.size();
    euler.push_back(v);
    eulerDepth.push_back(d);

    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v, d + 1);
        euler.push_back(v);
        eulerDepth.push_back(d);
    }
}

void buildSparse() {
    int m = (int)euler.size();
    for (int i = 0; i < m; i++) {
        st[i][0] = i;
    }

    for (int i = 2; i <= m; i++) {
        lg[i] = lg[i / 2] + 1;
    }

    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i + (1 << j) <= m; i++) {
            int x = st[i][j - 1];
            int y = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (eulerDepth[x] < eulerDepth[y] ? x : y);
        }
    }
}

int lca(int a, int b) {
    int l = firstPos[a];
    int r = firstPos[b];
    if (l > r) swap(l, r);

    int j = lg[r - l + 1];
    int x = st[l][j];
    int y = st[r - (1 << j) + 1][j];
    return euler[eulerDepth[x] < eulerDepth[y] ? x : y];
}

int dist(int a, int b) {
    int c = lca(a, b);
    return depthv[a] + depthv[b] - 2 * depthv[c];
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0, 0);
    buildSparse();

    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << " " << dist(a, b) << '\n';
    }
}

Сложность этого решения¶

• DFS и построение Эйлерова обхода: O(n)
• Построение sparse table: O(n log n)
• Один запрос LCA: O(1)

Дополнительный пример для понимания¶

Пусть дерево такое:

graph TD
    n1[1] --> n2[2]
    n1 --> n3[3]
    n2 --> n4[4]
    n2 --> n5[5]
    n5 --> n9[9]
    n3 --> n6[6]
    n6 --> n7[7]
    n6 --> n8[8]

Найдём несколько LCA:

• LCA(4, 9) = 2
• LCA(7, 8) = 6
• LCA(4, 8) = 1
• LCA(5, 9) = 5

Обрати внимание на последний случай: если одна вершина является предком другой, то именно она и будет LCA.

Частые ошибки¶

1. Забыли укоренить дерево¶

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

2. Неправильно посчитали глубины¶

Если глубины неверные, то и подъём, и формула расстояния будут давать неправильный ответ.

3. Ошибка в таблице up¶

Очень важно корректно задать предка корня. Часто делают так:

• up[root][0] = root

Тогда подъёмы не выходят за границы.

4. Перепутали первое вхождение в Эйлеровом обходе¶

Для метода с RMQ нужно брать именно первое появление вершины в массиве.

5. Неверная оценка LOG¶

Нужно брать такое значение, чтобы 2^LOG было не меньше максимальной высоты дерева.

Обычно достаточно:

• LOG = 20 для n <= 2 * 10^5
• LOG = 25 для n <= 10^7 не нужен в типичных задачах

На практике удобно писать:

const int LOG = 20; или 21, 22 — с запасом под ограничения задачи.

Что важно запомнить¶

• LCA — это самая глубокая общая вершина-предок двух узлов.
• Задача очень часто встречается в деревьях.
• Расстояние между вершинами легко выражается через LCA.
• Для практики чаще всего удобнее двоичный подъём.
• Идея из книги: LCA можно свести к RMQ на Эйлеровом обходе.

Краткое резюме¶

Если нужен простой и сильный метод¶

Берите двоичный подъём.

Если нужен очень быстрый ответ на запрос¶

Берите Эйлеров обход + sparse table.

Если задача про расстояния¶

Сначала находите LCA, затем используйте формулу:

dist(a, b) = depth[a] + depth[b] - 2 * depth[LCA(a, b)]