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

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

Перед прочтением рекомендуется вспомнить свойства массивов $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)$ памяти на предподсчет — лестничная декомпозиция.

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

Когда используется одновременно и глубина, и структура дерева, обычно помогает взглянуть на задачу геометрически. Сопоставим каждой вершине точку $(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$ . А именно, это будут ровно те ребра, которые встречались на этом отрезке ровно один раз — все, которые встречались дважды, ведут в какие-то побочные поддеревья.

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