Мо на деревьях
Материал из Algocode wiki
Пусть нам дана задача с оффлайн-запросами на пути в дереве (величины записаны на ребрах). В ней можно применить стандартный алгоритм Мо, но сначала надо выполнить подготовительные операции:
- Выпишем эйлеров обход дерева -- при каждом проходе по ребру выписываем номер ребра.
- Получив запрос, выделим его как подотрезок эйлерова обхода
- Заметим, что если ребро на отрезке встречалось дважды, то это было ребро, которое на пути не лежало -- оно вело в какое-то побочное поддерево.
Значит, в нашей структуре теперь нужно считать, сколько раз на отрезке встречается каждое ребро, а в основной структуре (которая считает ответ) надо учитывать только те ребра, которые сейчас встречаются единожды
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s