Конспект: запросы к дереву

Понятия

LCA(u, v) - самая глубокая вершина, являющаяся предком обеих (вершина - предок самой себя).

Расстояние в дереве: dist(u, v) = depth[u] + depth[v] − 2·depth[LCA(u, v)].

Проверка «предок ли»: tin[u] <= tin[v] и tout[v] <= tout[u] - O(1) после обхода.

Двоичные подъёмы: up[v][k] - предок на 2^k шагов, up[v][k] = up[up[v][k−1]][k−1].

RMQ - минимум на отрезке неизменяемого массива. Разреженная таблица: st[k][i] - минимум на отрезке длиной 2^k; запрос - минимум двух ПЕРЕКРЫВАЮЩИХСЯ отрезков.

Эйлеров обход - массив длины 2V − 1: вершина выписывается при входе и после возврата из каждого ребёнка.

Диаметр дерева - два обхода: от любой вершины к самой дальней b, от b к самой дальней. Перекоренение - ответ сына из ответа отца поправкой за ребро: для суммы расстояний S(v) = S(отец) − size(v) + (n − size(v)).

Слияние меньшего в большее - забрать самый большой набор ребёнка, влить меньшие: ≤ log₂ n переносов на элемент.

Тяжело-лёгкая декомпозиция - ребро к сыну с наибольшим поддеревом тяжёлое, цепочки подряд в массиве; путь - ≤ 2·log₂ n отрезков, запрос O(log² n).

Центроид - вершина, после удаления которой части ≤ m/2. Центроидная декомпозиция - пути через центроид, удаление, рекурсия; ≤ log₂ n уровней.

Что унести

LCA двоичными подъёмами:
  1) выровнять глубины подъёмом по битам разницы
  2) если вершины совпали - одна была предком другой (ЭТА ПРОВЕРКА ОБЯЗАТЕЛЬНА)
  3) прыгать обеими от БОЛЬШИХ k к меньшим, пока предки РАЗЛИЧАЮТСЯ
  4) ответ - up[u][0]

Разреженная таблица работает только для ИДЕМПОТЕНТНЫХ операций (f(x, x) = x): минимум, максимум, НОД. Для суммы перекрытие посчитало бы общую часть дважды.

Сведение LCA к RMQ: наименьший общий предок - вершина минимальной ГЛУБИНЫ между первыми вхождениями в массив эйлерова обхода (обход не перейдёт из одного поддерева в другое, минуя общего предка, и выше него не поднимется).

Тихие ошибки: пропустить проверку u == v после выравнивания (ответ на уровень выше); перебирать k по возрастанию; поставить корню parent = −1 вместо себя; брать минимум по номерам вершин вместо глубин; строить разреженную таблицу на меняющемся массиве.

Общий приём главы: дорогой повторяющийся путь разбивают на куски длиной в степень двойки и предподсчитывают их - так устроены и подъёмы, и разреженная таблица.

Общий мотив четырёх приёмов - удвоение: переносимый элемент попадает в набор вдвое больше, подъём по лёгкому ребру удваивает поддерево, центроид делит хотя бы пополам. Отсюда везде log n.

Куда это ведёт

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