Корневые деревья

Корневые деревья

Дерево называется корневым, если оно ориентированно и из какой-то вершины можно попасть во все остальные — такая вершина единственная, и она называется корнем.

Примеры корневых деревьев:

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

dfs
dfs

Напоминание: DFS

Посчитаем для каждой вершины времена входа (\(tin\)) и выхода (\(tout\)) из неё во время эйлерова прохода.

vector<int> g[maxn];
int p[maxn], tin[maxn], tout[maxn];
int t = 0;

void dfs (int v) {
    tin[v] = t++;
    for (int u : g[v])
        dfs(u);
    tout[v] = t; // при выходе из вершины можно тоже счётчик увеличить, но автор не хочет 
}

У этих массивов много полезных свойств:

Запросы на поддеревьях

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

Есть корневое дерево. Рядом с каждой вершиной записано число. Два типа запросов: прибавить ко всем вершинам на каком-то поддереве число \(x_i\) и найти значение числа у вершины \(v_i\).

Давайте запишем все числа у вершин в позиции, соответствующие \(tin\)-ам их вершин. Что такое «прибавить на поддереве» с точки зрения этого массива? Это то же, самое, что прибавить какую-то константу на каком-то подотрезке, а это можно делать какой-нибудь достаточно продвинутой структурой.

Запросы на уровнях

Дано корневое дерево. Требуется отвечать на запросы нахождения \(d_i\)-того предка вершины \(v_i\) (т. е. вершины-предка, находящейся на расстоянии \(d_i\)).

Создадим \(h\) векторов, где \(h\) — высота дерева. В каждый вектор добавим все вершины на этой глубине в том порядке, в котором мы в них заходили в dfs. Как следствие, они будут отсортированы по их \(tin\)-ам.

Теперь заметим, что отрезки их поддеревьев — \([tin_v, tout_v)\) — тоже не пересекаются, а значит ещё и отсортированы. Тогда мы можем просто взять \(tin\) вершины-запроса, посмотреть на вектор нужного уровня и сделать бинпоиск по нужному отрезку.

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

Очень много задач нам поможет решить следующая вспомогательная задача.

Дано корневое дерево. Требуется отвечать на запросы нахождения наименьшего общего предка вершин \(u_i\) и \(v_i\), то есть вершины \(w\), которая лежит на пути от корня до \(u_i\), на пути от корня до \(v_i\), и при этом самую глубокую (нижнюю) из всех таких.

По-английский эта задача называется Least Common Ancestor. Есть много разных способов её решать, и мы рассмотрим основные.

lca
lca

Для лучшего понимания: медленно (за линейное время) это можно делать так:

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

int lca (int u, int v) {
    while (!ancestor(u, v))
        u = p[u];
    return u;
}

LCA: двоичные подъемы

Предпосчитаем для каждой вершины её 1-го предка, 2-го предка, 4-го, и т.д. Сохраним это всё в двумерном массиве up размера \(n \times \lceil \log n \rceil\) — столько точно хватит. В up[v][d] будет храниться предок вершины \(v\) на расстоянии \(2^d\), а если такой вершины не существует — то корень.

Такой препроцессинг можно выполнить за \(O(n \log n)\), используя тот факт, что предок на расстоянии \(2^{d+1}\) — это предок на расстоянии \(2^d\) предка на расстоянии \(2^d\):

int up[maxn][logn];

void dfs (int v) {
    for (int l = 1; l < logn; l++)
        up[v][l] = up[up[v][l-1]][l-1];
    tin[v] = t++;
    for (int u : g[v]) {
        up[u][0] = v;
        dfs(u);
    }
    tout[v] = t;
}

Пусть поступил очередной запрос — пара вершин \((u, v)\):

Подробнее про второй пункт. Пусть \(L = \lceil \log n \rceil\). Присвоим \(i = L\). Будем уменьшать эту переменную на единицу, пока up[v][i] не перестанет быть предком \(u\) (указатель up[v][i] изначально будет корнем, а затем каждую итерацию спускаться на \(2^i\)). Когда это произойдёт, подвинем указатель на \(2^i\)-го предка \(v\), и продолжим дальше. Мы можем это делать, потому что два раза прыгать на {2^i} — можно один раз прыгнуть на \(2^{i+1}\).

int lca (int v, int u) {
    if (a(v, u)) return v;
    if (a(u, v)) return u;
    for (int l = logn-1; l >= 0; l--)
        if (!ancestor(up[v][l], u))
            v = up[v][l];
    return up[v][0];
}

Асимптотика

Препроцессинг — \(O(n \log n)\). Размер массива up ровно такой, и каждый его элемент вычисляется за константу.

Ответ на запрос — \(O(\log n)\), потому что по сути мы делаем один бинпоиск.

Запросы на путях

Пусть нас вместо LCA спрашивают, например, о минимуме на произвольном пути (на всех рёбрах записаны какие-то числа).

Мы можем сделать такой же предподсчет, как в методе двоичных подъемов, но хранить вместе с номером \(2^d\)-го предка минимум на соответствующем пути.

Мы знаем, что минимум на пути от \(u\) до \(v\) — это минимум от минимума на пути от \(u\) до \(lca(u, v)\) и от минимума на пути от \(v\) до \(lca(u, v)\). А каждый минимум — это минимум на всех двоичных подъемах до LCA.

int get_min (int v, int u) {
    int ans = inf;
    for (int l = logn-1; l >= 0; l--)
        if (!ancestor(up[v][l], u))
            v = up[v][l], ans = min(ans, mn[v][l]);
    for (int l = logn-1; l >= 0; l--)
        if (!ancestor(up[u][l], v))
            u = up[u][l], ans = min(ans, mn[u][l]);
    return min({ans, mn[v][0], mn[u][0]})
}

Аналогичным образом можно считать сумму, gcd, полиномиальный хэш и много других странных функций на пути, но только в статичном случае (т. е. когда у нас нет обновлений). Для динамического случая существует heavy-light декомпозиция, но она очень сложная.

Сведение к RMQ

Другая идея — это пройтись dfs-ом и выписать два массива: глубины вершин и их номера. Выписывать их мы будем как когда будем входить в вершину, так и когда выходить.

Во втором массиве мы по сути выписали наш проход dfs-а.

Заметим, что размер полученного массива — \(O(n)\). Доказательство — каждое ребро мы пройдем дважды (заходя в и выходя из поддерева), при просмотре каждого ребра мы выпишем не более, чем две вершины (потому что у каждого ребра всего два конца). Тогда размер массива не более, чем в четыре раза больше числа ребер, которых \(n-1\).

Пусть у нас есть запрос: найти LCA вершин \(v\) и \(u\). Для определенности положим, что \(tin_v < tin_u\). Посмотрим на наш выписанный путь между тем моментом, когда мы вышли из \(v\) и в первй раз вошли в \(u\). Где-то на выписанном пути мы должны были прийти в наименьший общий предок, потому что любой простой путь между двумя вершинами в дереве единственный. При этом, мы не поднимались никогда из LCA куда-то выше, а значит LCA — это самая высокая вершина на этом пути.

Получается, что можно найти LCA, просто найдя позицию минимума на отрезке \([tout_v, tin_u]\) в массиве глубин, и посмотрев, какой вершине она соответствует в эйлеровом обходе. Получается, задачу LCA можно свести к RMQ (нахождению минимума на отрезке), что мы уже умеем.

Разреженная таблица

На практике асимптотику мы особо не улучшили — пока что всё равно требуется \(O(n \log n)\) времени на запрос в ДО, хоть преподсчёт и будет уже линейным. Асимптотику можно улучшить, используя тот факт, что мы решаем static RMQ, то есть у нас нет изменений этого массива.

Помимо ДО, есть более крутая структура, позволяющая отвечать на запрос минимума за \(O(1)\), но использующая \(O(n \log n)\) препроцессинга (с очень маленькой константой). Подробнее вы можете почитать в отдельной статье.

А наоборот можно?*

Примечание: алгоритм (Фарах-Колтона и Бендера), описаный в этой секции, абсолютно бесполезен на практике, однако очень интересен с теоретической точки зрения.

Интересный с теоретической точки зрения факт: LCA сводится к RMQ без изменения асимптотики, но не наоборот. Почему это так? Потому что на самом деле мы работаем не со всеми массивами целых чисел от 1 до \(n\), а только с некоторыми — любые два элемента отличаются ровно на единицу, потому что они соответствуют либо спуску, либо подъему в dfs. Выясняется, что это ограничение позволяет находить минимум на подобных массивах за константное время работы как на препроцессинг, так и на запрос. Наоборот, к несчатью, свести нельзя.

Сделаем следующее: раз каждые два элемента отличаются на единицу, сопоставим исходнуму массиву глубин булевый массив размера \(n-1\): единица стоит, если следующее значение больше, единица в противном случае ноль.

Возьмем константу \(k = \lfloor \frac{\log n}{2} \rfloor\), и разделим на блоки по столько элементов. На каждом блоек посчитаем минимум, а над всеми такими блоками построим sparse table. Всего блоков \(O(\frac{2 n}{\log n})\), и построение будет работать за линейное время:

\[O(\frac{2 n}{\log n} \log \frac{2 n}{\log n}) = O(\frac{2 n}{\log n} (\log 2n - \log \log n)) = O(n)\]

Также посчитаем для каждой возможной маски размера \(\frac{\log n}{2}\) минимум на ней — это можно сделать за их количество, помноженное на длину маски а их немного: всего \(\sqrt n\) (ради этого мы и делили логарифм на два).

ОК. Что теперь можно сделать во время запроса? Запрос — это какой-то отрезок. Он включает в себя какие-то последовательные блоки, и сколько-то ячеек слева и справа, не вошедшие ни в какой цельный блок. Для блочной части мы можем сделать запрос в sparse table — он будет работать за константу.

Не-блочная часть хоть и маленькая, но мы всё же заявили, что будем обрабатывать запросы за константу, и сдержим свое слово. Мы возмем левую не-блочуню часть запроса и возьмем оттуда маску — это можно сделать за константу. Тогда минимум на не-блочной части — это минимум на левом блочном элементе минум минимум на не-блочной маски, которую мы предпосчитали.

Чуть более подробно и с реализацией (автор это никогда не кодил и вам не советует) можно почитать у Емакса.

Впрочем, этот алгоритм на практике использовать нецелесообразно: у него слишком большая константа. Слишком много чего нужно считать, чтобы выкинуть этот логарифм из асимптотики.

Важный вывод такой: RMQ более общая задача, чем LCA. UPD: это неправда, я глупый.