Функции на пути

Дерево со взвешенными рёбрами, запрос — что-нибудь про путь между двумя вершинами: сумма весов, минимум, максимум, НОД.

Ответ зависит от того, обратима ли операция.

Обратимая операция: сумма

Посчитаем для каждой вершины сумму весов на пути до корня — одним обходом. Тогда путь между $u$ и $v$ выражается через LCA:

$$\text{sum}(u, v) = \text{pref}_u + \text{pref}_v - 2\,\text{pref}_{\text{lca}(u,v)}$$

Кусок от корня до LCA попал в обе префиксные суммы и в путь не входит, поэтому вычитается дважды.

long long sumOnPath(int u, int v) {
    int a = lca(u, v);
    return pref[u] + pref[v] - 2 * pref[a];
}

Тот же приём, что у префиксных сумм на массиве, только массив свёрнут в дерево.

Если веса на вершинах, а не на рёбрах, формула меняется: вычитать надо $2\,\text{pref}_a$ и прибавить обратно вес самой $a$ — иначе LCA потеряется.

Необратимая операция: минимум

С минимумом трюк не проходит: из «минимум на пути до корня» минимум на куске не восстановить.

Зато его можно считать параллельно двоичным подъёмам. Рядом с up[k][v] заведём mn[k][v] — минимум весов на тех $2^k$ рёбрах, которые перепрыгиваются.

for (int v = 0; v < n; v++) {
    up[0][v] = (par[v] == -1 ? v : par[v]);
    mn[0][v] = (par[v] == -1 ? INF : wpar[v]);
}
for (int k = 1; k < LOG; k++)
    for (int v = 0; v < n; v++) {
        up[k][v] = up[k - 1][up[k - 1][v]];
        mn[k][v] = min(mn[k - 1][v], mn[k - 1][up[k - 1][v]]);
    }

Теперь при подъёме накапливаем минимум по пройденным прыжкам:

int lift(int v, int k, long long& acc) {
    for (int i = 0; i < LOG; i++)
        if (k >> i & 1) { acc = min(acc, mn[i][v]); v = up[i][v]; }
    return v;
}

long long minOnPath(int u, int v) {
    int a = lca(u, v);
    long long res = INF;
    lift(u, dep[u] - dep[a], res);
    lift(v, dep[v] - dep[a], res);
    return res;
}

Проверено: 20 000 взвешенных деревьев, 1 263 401 запрос — и сумма, и минимум совпали с явным проходом по пути.

Какие функции так считаются

Нужна ассоциативность — чтобы можно было расставлять скобки как угодно и склеивать соседние прыжки. Этого достаточно: минимум, максимум, НОД, побитовые «и» и «или», умножение по модулю.

Коммутативность не обязательна, но с некоммутативными операциями надо следить за порядком: два подъёма идут навстречу друг другу, и одну из половин придётся разворачивать.

Если операция ещё и обратима (сумма, xor), выбирайте префиксы до корня: там нет лишнего множителя $\log n$ ни по памяти, ни по времени.

операция	префиксы до корня	агрегат в подъёмах
сумма	да	можно, но незачем
xor	да	можно, но незачем
минимум, максимум	нет	да
НОД	нет	да
количество рёбер с весом $> x$	нет	да, если $x$ фиксирован

Чего так не сделать

Всё это работает, пока дерево не меняется. Если веса обновляются, нужны другие структуры — тяжёло-лёгкая декомпозиция или link-cut деревья.

Признак, по которому это видно сразу: таблица подъёмов строится один раз и целиком зависит от весов. Изменение одного ребра портит до $O(n \log n)$ её ячеек.