Алгоритм Мо на дереве: как свести запросы на путях к запросам на отрезке?
Понял Мо на массиве. А как применить его к запросам на дереве — например, «сколько различных значений на пути от u до v»? Дерево — не линейный массив, непонятно, как тут вообще скользить указателями.
2 ответа
Идея — линеаризовать дерево эйлеровым обходом по входам/выходам, чтобы путь превратился в отрезок, к которому уже применим обычный Мо.
Делаем DFS и для каждой вершины записываем два тайм-штампа: tin[v] (при заходе) и tout[v] (при выходе), добавляя вершину в линейный массив euler дважды — при заходе и при выходе. Тогда для запроса (u, v):
- Пусть
tin[u] <= tin[v](иначе поменяем). Обозначимl = LCA(u, v). - Если
l == u(u — предок v): берём отрезокeuler[tin[u] .. tin[v]]. - Иначе: берём
euler[tout[u] .. tin[v]]и дополнительно учитываем сам LCAl.
Ключевой трюк add/remove: вершина, встретившаяся в отрезке эйлерова массива дважды (и tin, и tout), фактически не на пути — её «включение» и «выключение» компенсируются. Поэтому делаем переключатель: при обработке элемента, если вершина сейчас «активна» — убираем её, иначе добавляем (toggle по чётности появлений). LCA, если он не попал в отрезок, добавляем отдельно до снятия ответа и убираем после.
Сортировка запросов — та же, что в обычном Мо, по блокам индекса левой границы в euler. Сложность та же O((n + q) sqrt n) плюс O(log n) на LCA-предподсчёт (двоичные подъёмы / Эйлер + RMQ). Память O(n).
Это рабочая, но тонкая в реализации техника — главное аккуратно описать четыре случая (l == u или нет) и toggle-логику.
Грабля номер один — не забыть отдельный учёт LCA в случае, когда u и v в разных поддеревьях: при отрезке [tout[u], tin[v]] сама вершина LCA в этот отрезок не входит (её tin раньше tout[u]), а на пути она есть. Перед снятием ans делаешь add(l), после — remove(l). Если этого не сделать — стабильный WA ровно на «диагональных» путях, который сложно поймать на маленьких тестах. Альтернатива всему этому, если значения только в вершинах и запросы простые, — иногда проще small-to-large merge или persistent-структуры; Мо на дереве берут, когда функция тяжело декомпозируется иначе.