Пусть у нас есть значения в вершинах (если на ребрах, то все хорошо и никаких проблем нет) и хотим отвечать на запросы на путях с помощью Мо.

Стандартная реализация работала бы примерно так:

    move l, r
    ...
    if (u != lca && v != lca) toggle(lca);
    ans[query_id] = ...;
    if (u != lca && v != lca) toggle(lca);

Что вполне нормально, если включение/выключение вершины работает за $$$O(1)$$$, но это не всегда так. У нас может быть какой-то набор значений в вершине $$$v$$$ и включение требует $$$size(values[v])$$$ операций. Тогда эта лишняя проверка сломает ассимптотику.

У меня есть несколько идей как это можно было бы исправить:

1) Как-то поменять алгоритм чтобы не приходилось дополнительно проверять LCA

2) Изменить сортировку, чтобы получить небольшое количество отрезков запросов, на которых lca один и тот же. Тогда можно один раз включать его в начале отрезка запросов и выключать в конце.

3) Сделать новое дерево, где в каждой вершине лежит только одно значение, но при это все так же возможно представить любой путь как отрезок (не повысив при этом суммарный размер слишком сильно)

Но у меня нет идей как делать что-либо из этого. Буду рад помощи)