Euler Tour и LCA (Binary Lifting)

Дерево — это особый граф

1. Между любыми двумя вершинами ровно один путь
2. Удаление любого ребра разбивает граф на две компоненты
3. Можно выбрать корень → появляется иерархия (родитель, потомки, поддерево)

Граф с циклом:
1 — 2 — 3
|       |
4 — 5 — 6

Дерево:
    1
   / \
  2   3
 / \   \
4   5   6

Задача: e-olymp 11429 — Подчинённые

     1
    / \
   2   3
  / \
 4   5

Ответ: сотрудник 1 → 4, сотрудник 2 → 2, сотрудники 3, 4, 5 → 0

Как бы вы решили эту задачу?

DFS на дереве — без visited[]

1. В дереве нет циклов → DFS не может вернуться в уже посещённую вершину (кроме родителя)
2. Вместо visited[] достаточно передавать параметр parent
3. DFS из корня обходит каждую вершину ровно раз и задаёт естественный порядок обхода

void dfs(int v, int parent) {
    for (int u : adj[v]) {
        if (u != parent) {
            dfs(u, v);
        }
    }
}
  

Укоренение дерева: parent[] и depth[]

Задача: дано дерево, корень = 1. Для каждой вершины найти parent[v] и depth[v].

vector<int> adj[MAXN];
int parent[MAXN], depth[MAXN];

void dfs(int v, int p, int d) {
    parent[v] = p;
    depth[v] = d;
    for (int u : adj[v]) {
        if (u != p) {
            dfs(u, v, d + 1);
        }
    }
}

// Вызов: dfs(1, 0, 0);
  

depth 0:       1
depth 1:      / \
             2   3
depth 2:    / \   \
           4   5   6

Размер поддерева через DFS

• sz[v] = количество вершин в поддереве v (включая саму v)
• sz[v] = 1 + Σ sz[u] для всех детей u вершины v
• Ответ на задачу: подчинённых у v = sz[v] − 1

int sz[MAXN];

void dfs(int v, int p) {
    sz[v] = 1;
    for (int u : adj[v]) {
        if (u != p) {
            dfs(u, v);
            sz[v] += sz[u];
        }
    }
}
  

     1 (sz=5)
    / \
(sz=3)2   3(sz=1)
  / \
(1)4   5(1)

Ответ: подчинённых[1]=4, [2]=2, [3]=0, [4]=0, [5]=0

Порядок обхода DFS = линейный порядок вершин

     1
    / \
   2   5
  / \
 3   4

Порядок: 1, 2, 3, 4, 5
(нумерация по времени входа)

Задача: проверка предка за O(1)

• Наивно: подняться от v к корню, проверить, встретим ли u → O(n) на запрос → TLE
• Идея: если поддерево u — отрезок, то v ∈ поддерево(u) ⇔ v попадает в этот отрезок

Нам нужны два числа для каждой вершины

• Чтобы задать отрезок [начало, конец] для поддерева v, нужно знать:
• Когда DFS вошёл в вершину v → tin[v]
• Когда DFS вышел из вершины v → tout[v]

Тогда: поддерево v = все вершины u, где tin[v] ≤ tin[u] ≤ tout[v]

Euler Tour: tin[] и tout[]

int timer = 0;
int tin[MAXN], tout[MAXN];

void dfs(int v, int p) {
    tin[v] = timer++;
    for (int u : adj[v]) {
        if (u != p) {
            dfs(u, v);
        }
    }
    tout[v] = timer - 1;
}
  

Мы используем: tout[v] = timer - 1 (закрытый отрезок)

Поддерево v = отрезок [tin[v], tout[v]]

Пример Euler Tour

       1
      /|\
     2  3  4
    / \    |
   5   6   7

DFS: 1, 2, 5, 6, 3, 4, 7

Позиция:  0    1    2    3    4    5    6
Вершина:  1    2    5    6    3    4    7
          [--------1-----------------------]
               [----2--------]
                    [5]  [6]
                              [3]
                                   [----4----]
                                        [7]

Проверка: u предок v? → O(1)

Примеры (из предыдущего слайда):

• Является ли 2 предком 5? tin[2]=1 ≤ tin[5]=2 ✓ и tout[5]=2 ≤ tout[2]=3 ✓ → ДА
• Является ли 2 предком 7? tin[2]=1 ≤ tin[7]=6 ✓ но tout[7]=6 ≤ tout[2]=3? НЕТ

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
  

Главная идея: поддерево → отрезок

Пусть order[] — массив вершин в порядке tin. Тогда:

• Поддерево вершины v = order[tin[v] .. tout[v]]
• Это непрерывный подмассив длины sz[v]

Следствие — любая задача на поддереве сводится к задаче на отрезке массива:

• Сумма значений в поддереве → сумма на отрезке
• Минимум в поддереве → минимум на отрезке
• Обновление значений в поддереве → обновление на отрезке

Задача: сумма значений в поддереве

Решение:

1. Запускаем DFS, вычисляем tin[v]
2. Создаём массив a[] в Euler-порядке: a[tin[v]] = w[v]
3. Считаем префиксные суммы
4. Сумма в поддереве v = prefix[tout[v]+1] - prefix[tin[v]]

// После DFS (tin[], tout[] заполнены)
vector<long long> a(n), prefix(n + 1, 0);
for (int v = 1; v <= n; v++)
    a[tin[v]] = w[v];

for (int i = 0; i < n; i++)
    prefix[i + 1] = prefix[i] + a[i];

// Сумма в поддереве v:
long long subtree_sum = prefix[tout[v] + 1] - prefix[tin[v]];
  

Сложность: O(n) предвычисление, O(1) на запрос

Euler Tour: полная реализация

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

const int MAXN = 200005;
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN], sz[MAXN], depth[MAXN], parent[MAXN];
int timer = 0;
int order[MAXN];  // order[i] = вершина с tin = i

void dfs(int v, int p, int d) {
    parent[v] = p;
    depth[v] = d;
    tin[v] = timer;
    order[timer] = v;
    timer++;
    sz[v] = 1;
    for (int u : adj[v]) {
        if (u != p) {
            dfs(u, v, d + 1);
            sz[v] += sz[u];
        }
    }
    tout[v] = timer - 1;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0, 0);
    // Поддерево v = отрезок [tin[v], tout[v]]
    // sz[v] == tout[v] - tin[v] + 1
    return 0;
}
  

Проверка: sz[v] == tout[v] - tin[v] + 1

Осторожно: глубина рекурсии

Проблема: при n = 200000 и дереве-«бамбуке» глубина рекурсии = n
Стандартный стек = 1–8 МБ → segmentation fault

Решения:

1. Увеличить стек (Linux: ulimit -s unlimited)
2. Итеративный DFS (сложнее, но возможно)
3. На IOI: обычно стека хватает (256MB stack)

Практика: 20 минут

Перерыв после практики: 15:45–16:00

LCA — Lowest Common Ancestor

       1
      / \
     2   3
    / \   \
   4   5   6
  /
 7

Зачем нужен LCA?

1. Расстояние между вершинами:
   dist(u, v) = depth[u] + depth[v] − 2·depth[LCA(u, v)]
2. Путь между вершинами: путь u→v проходит через LCA(u, v)
3. Запросы на путях: сумма/минимум на пути = объединение двух вертикальных путей через LCA
4. Продвинутые структуры: HLD, virtual tree, auxiliary tree

Задача: e-olymp 3298 — Общий предок

• Предобработка за O(n log n) или лучше
• Каждый запрос за O(log n) или лучше

Начнём с наивного алгоритма, потом ускорим.

Наивный LCA: выравнивание + подъём

1. Выравнивание глубин: если depth[u] > depth[v], поднимаем u вверх
2. Одновременный подъём: поднимаем u и v по одному ребру вверх, пока u ≠ v
3. Когда u == v — это LCA

Шаг 1: depth[7]=3, depth[6]=2 → поднимаем 7→4 (depth=2)
Шаг 2: u=4, v=6. Поднимаем оба: 4→2, 6→3
Шаг 3: u=2, v=3. Поднимаем оба: 2→1, 3→1. u==v!
Ответ: LCA(7, 6) = 1

Наивный LCA: код

int lca_naive(int u, int v) {
    // Шаг 1: выравниваем глубины
    while (depth[u] > depth[v]) u = parent[u];
    while (depth[v] > depth[u]) v = parent[v];
    // Шаг 2: поднимаемся вместе
    while (u != v) {
        u = parent[u];
        v = parent[v];
    }
    return u;
}
  

• Сложность: O(n) в худшем случае (дерево-бамбук)
• При q = 200000 запросов → O(n·q) = O(4·10¹⁰) — TLE

Идея: прыгать не по 1, а по 2^k

• Если мы заранее знаем «предок на расстоянии 2^k» для каждой вершины:
• Подняться на h шагов = O(log h) прыжков
• Каждый прыжок — O(1) (таблица предвычислена)

Binary Lifting: таблица up[v][k]

• База: up[v][0] = parent[v] (предок на расстоянии 1)
• Рекуррентность: up[v][k] = up[ up[v][k-1] ][k-1]
• Подняться на 2^k = подняться на 2^k-1, потом ещё на 2^k-1

up[v][2] = предок на 4:

v --------→ up[v][1] --------→ up[v][2] = up[up[v][1]][1]
     2^1=2               2^1=2

Размер таблицы: n × LOG, где LOG = ⌈log₂n⌉ ≈ 18 для n = 200000

Предвычисление up[][]

const int LOG = 18;  // ceil(log2(200000)) = 18
int up[MAXN][LOG];

void preprocess(int root) {
    // Сначала DFS для parent[] и depth[]
    dfs(root, 0, 0);

    // Заполняем таблицу
    for (int v = 1; v <= n; v++)
        up[v][0] = parent[v];

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

• Внешний цикл по k — по уровню (от маленьких к большим)
• Порядок важен: для k нужны значения k−1, которые уже вычислены
• Соглашение: up[root][k] = 0 для всех k (вышли за корень)

Сложность: O(n log n) по времени и памяти

Пример таблицы up[][]

       1
      / \
     2   3
    / \
   4   5
  /
 6

LCA, Шаг 1: выравнивание глубин

Привести u и v к одной глубине: разложить diff в двоичную систему

// Шаг 1: выравнивание
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; k++) {
    if ((diff >> k) & 1) {
        u = up[u][k];
    }
}
// Теперь depth[u] == depth[v]
  

LCA, Шаг 2: поднимаемся вместе

После шага 1: depth[u] == depth[v]. Если u == v — готово. Иначе:

Пример: LCA(7, 5)

          1
         / \
        2   3
       /|\   \
      4  5  8  6
     /       \
    7         9

Пример: LCA(9, 5) — с реальными прыжками

Дерево со слайда 7.6. parent: 9→8, 8→3, 3→1, 5→2, 2→1

Полный код: LCA за O(log n)

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

const int MAXN = 200005;
const int LOG = 18;

vector<int> adj[MAXN];
int depth[MAXN], up[MAXN][LOG];
int n;

void dfs(int v, int p, int d) {
    depth[v] = d;
    up[v][0] = p;
    for (int k = 1; k < LOG; k++)
        up[v][k] = up[ up[v][k-1] ][k-1];
    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v, d + 1);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];

    for (int k = 0; k < LOG; k++)
        if ((diff >> k) & 1)
            u = up[u][k];

    if (u == v) return u;

    for (int k = LOG - 1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return up[u][0];
}

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

    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}
  

Сложность: O(n log n) предобработка, O(log n) на запрос

Сложность Binary Lifting

Для n = q = 200000, LOG = 18: предобработка ~3.6M операций, память ~14 МБ

Применение 1: расстояние в дереве за O(log n)

• Путь u → v проходит через LCA(u, v)
• Длина u → LCA = depth[u] − depth[LCA]
• Длина LCA → v = depth[v] − depth[LCA]

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
  

Применение 2: k-й предок за O(log n)

int kth_ancestor(int v, int k) {
    for (int i = 0; i < LOG; i++) {
        if ((k >> i) & 1) {
            v = up[v][i];
        }
    }
    return v;  // 0 если вышли за корень
}
  

Задача: CSES 1687 «Company Queries I» — прямое применение

Практика: 40 минут

Последний час — решаем и обсуждаем. Задавайте вопросы!