Мо на деревьях

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

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

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

---

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

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