Мо на деревьях: различия между версиями

Текущая версия на 12:55, 28 сентября 2020

Пусть нам дана задача с оффлайн-запросами на пути в дереве (величины записаны на ребрах). В ней можно применить стандартный алгоритм Мо, но сначала надо выполнить подготовительные операции:

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

Значит, в нашей структуре теперь нужно считать, сколько раз на отрезке встречается каждое ребро, а в основной структуре (которая считает ответ) надо учитывать только те ребра, которые сейчас встречаются единожды

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s

@@ Строка 1: / Строка 1: @@
 Пусть нам дана задача с оффлайн-запросами на пути в дереве (величины записаны на ребрах). В ней можно применить стандартный [[алгоритм Мо]], но сначала надо выполнить подготовительные операции:
-* Выпишем эйлеров обход дерева --- при каждом проходе по ребру выписываем номер ребра.
+* Выпишем эйлеров обход дерева -- при каждом проходе по ребру выписываем номер ребра.
 * Получив запрос, выделим его как подотрезок эйлерова обхода
-* Заметим, что если ребро на отрезке встречалось дважды, то это было ребро, которое на пути не лежало --- оно вело в какое-то побочное поддерево.
+* Заметим, что если ребро на отрезке встречалось дважды, то это было ребро, которое на пути не лежало -- оно вело в какое-то побочное поддерево.
 Значит, в нашей структуре теперь нужно считать, сколько раз на отрезке встречается каждое ребро, а в основной структуре (которая считает ответ) надо учитывать только те ребра, которые сейчас встречаются единожды