Мо на дереве

Алгоритм Мо работает с отрезком массива. Путь в дереве отрезком не является - но им становится после правильной нумерации.

Обход, в котором каждая вершина дважды

Запустим обход в глубину и будем выписывать вершину дважды: в момент входа $tin_v$ и в момент выхода $tout_v$. Получится массив длины $2n$.

stack.push_back(root);
tin[root] = timer; order[timer++] = root;
while (!stack.empty()) {
    int v = stack.back();
    if (at[v] < (int) children[v].size()) {
        int to = children[v][at[v]++];
        tin[to] = timer; order[timer++] = to;
        stack.push_back(to);
    } else {
        tout[v] = timer; order[timer++] = v;
        stack.pop_back();
    }
}

Обход без рекурсии - не педантизм: дерево может оказаться цепочкой, и на ста тысячах вершин рекурсия уже падает.

Путь как отрезок

Пусть $tin_u \le tin_v$ и $l = \mathrm{lca}(u, v)$. Тогда

случай	отрезок	общий предок
$l = u$	$[tin_u,\ tin_v]$	входит в отрезок
$l \ne u$	$[tout_u,\ tin_v]$	не входит, учитывается отдельно

Свойство, на котором всё держится: в этом отрезке вершины пути встречаются ровно один раз, а все прочие - ровно два или ни разу.

Почему так. Если вершина $w$ не на пути и её поддерево не пересекает отрезок, она не встретится вовсе. Если её поддерево целиком внутри - встретятся оба вхождения, вход и выход. А для вершины пути внутрь отрезка попадает ровно одно из двух вхождений: второе осталось по другую сторону от границы.

Переключение вместо добавления

Раз присутствие вершины определяется чётностью числа вхождений, add и del сливаются в одну функцию:

auto toggle = [&](int i) {
    int v = order[i];
    if (inside[v]) remove(value[v]);
    else add(value[v]);
    inside[v] ^= 1;
};

Дальше всё как в обычном Мо: те же четыре цикла по границам, тот же порядок обхода, только блок берётся $2n/\sqrt q$ - массив вдвое длиннее.

Общий предок

Во втором случае $l$ в отрезок не попадает: его вход раньше $tout_u$, а выход позже $tin_v$. Поэтому его надо учесть вручную - и способ зависит от вопроса:

• количество различных: прибавить единицу, если такого значения на пути ещё нет;
• количество пар равных: прибавить текущий счётчик его значения;
• $k$-е по величине: временно добавить его в счётчики, ответить, сразу убрать.

Числа на рёбрах. Отдайте каждое ребро его нижнему концу - тогда рёбра пути это вершины пути, кроме общего предка. Отрезок подбирается так, чтобы предок в него не попал: $[tin_u + 1,\ tin_v]$ в первом случае и тот же $[tout_u,\ tin_v]$ во втором. Никакого отдельного учёта тогда не нужно.

Итого $O(n\sqrt q)$ на обход плюс $O(n \log n)$ на подготовку общих предков.