Запросы на деревьях - Алгоритмика
Запросы на деревьях

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

автор Сергей Слотин
пререквизиты Поиск в глубину Запросы на отрезках Дерево отрезков

В этой статье мы рассмотрим различные методы сведения задач на деревьях к задачам на отрезках, которые можно решать уже известными структурами данных.

Перед прочтением рекомендуется вспомнить свойства массивов $tin$ и $tout$, получаемых обходом в глубину.

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

Первым важным свойством dfs является то, что $tin$-ы вершин любого поддеререва являются каким-то непрерывным отрезком.

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

Сумма на поддереве

Задача. Дано корневое дерево. Рядом с каждой вершиной записано число. Поступают два типа запросов: изменить какое-то из значений и найти сумму значений на поддереве вершины $v_i$.

Выпишем все числа у вершин в один массив в позиции, соответствующие их $tin$-ам. Что такое «сумма на поддереве $v$» в терминах этого массива? Это просто сумма на подотрезке $[tin_v, tout_v)$.

Построим поверх массива дерево отрезков или любую другую структуру для динамической суммы, и для запросов первого типа будем отправлять структуре запрос изменения ячейки $a_{tin_v} = x$, а для второго будем делать запрос суммы на подотрезке $[tin_v, tout_v)$.

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

Помимо $tin$ и $tout$ бывает полезно во время обхода считать глубину вершины. Будем в дальнейшем обозначать её за $depth_v$.

Level Ancestor

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

Создадим $h$ векторов, где $h$ — высота дерева. Для каждой вершины, во время прохода в dfs, добавим её $tin$ в вектор, соответствующей её глубине. Получаем $h$ отсортированных векторов.

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

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

Поддеревья заданной глубины

Задача. Дано корневое дерево. Рядом с каждой вершиной записано число. Поступают два типа запросов: изменить какое-то из значений и найти сумму значений на поддереве вершины $v_i$ среди вершин на расстоянии не более $k_i$ от неё.

Когда используется одновременно и глубина, и структура дерева, обычно помогает взглянуть на задачу геометрически. Сопоставим каждой вершине точку $(tin_u, depth_u)$. Тогда как выглядят искомые множества вершин? Они соответствуют тем точкам, у которых первая координата лежит между $tin_v$ и $tout_v$, а вторая больше $depth_v$.

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

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

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

Сумма на пути

Задача. Дано дерево. У каждого ребра есть какое-то число. Нужно отвечать на запросы нахождения суммы на пути.

Предподсчитаем во время обхода в глубину массив $s$, где $s_v$ это сумма чисел на пути от корня до вершины $v$.

Любой путь в дереве разбивается на один или два вертикальных пути. Найдем наибольшего общего предка $c = lca(a, b)$ и разобьём сумму как $(s_a + s_b - 2 \cdot s_c)$.

Xor на пути

Задача. Дано дерево. У каждого ребра есть какое-то число. Нужно отвечать на запросы нахождения xor-суммы на пути.

Заметим, что в случае с xor-суммой не нужно даже искать эти пути — по модулю двойки слагаемое $2 \cdot s_c$ «отменит» само себя. Достаточно просто вывести s[a] ^ s[b].

Число различных чисел на пути

Задача. Дано дерево. У каждого ребра есть какое-то число. Требуется отвечать на $q$ запросов нахождения числа различных значений на пути с $v$ по $u$.

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

  • Выпишем эйлеров обход дерева: при каждом проходе по ребру выписываем номер ребра (номер нижней/верхней вершины). Заметим, что каждое ребро будет выписано дважды: при входе и выходе из нижней вершины.
  • Получив запрос, определим «более раннюю» вершину $v$ (с меньшим $tin_v$) и рассмотрим подотрезок эйлерова обхода с $tin_v$ по $tin_u$.
  • Какая-то подпоследовательность ребер на этом отрезке является кратчайшим путем между $v$ и $u$. А именно, это будут ровно те ребра, которые встречались на этом отрезке ровно один раз — все, которые встречались дважды, ведут в какие-то побочные поддеревья.

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