Метод двоичных подъемов

В контексте решения задачи LCA и не только популярен следующий метод.

#Предподсчет

Предподсчитаем для каждой вершины её 1-го предка, 2-го предка, 4-го и так далее. Сохраним их в двумерном массиве up размера $n \times \lceil \log n \rceil$: в up[v][d] будет храниться предок вершины $v$ на расстоянии $2^d$, а если такой вершины не существует, то корень.

Такой препроцессинг можно выполнить за $O(n \log n)$, используя тот факт, что предок на расстоянии $2^{d+1}$ — это предок на расстоянии $2^d$ предка на расстоянии $2^d$:

int up[maxn][logn];

void dfs(int v) {
    for (int l = 1; l < logn; l++)
        up[v][l] = up[up[v][l-1]][l-1];
    tin[v] = t++;
    for (int u : g[v]) {
        up[u][0] = v;
        dfs(u);
    }
    tout[v] = t;
}

Препроцессинг суммарно занимает $O(n \log n)$ времени и памяти, потому что таков размер массива up, и каждый его элемент вычисляется за константу.

#Запрос

Пусть теперь поступил запрос нахождения LCA — пара вершин $(u, v)$:

• Проверим, не является ли одна вершина предком другой — в таком случае она и является результатом.
• Иначе, пользуясь массивом up, будем подниматься по предкам одной из них, пока не найдём самую высокую вершину, которая ещё не является предком другой. Следующая за ней будет искомым LCA.

Подробнее про второй пункт. Присвоим $i = \lceil \log n \rceil$ и будем уменьшать эту переменную на единицу, пока up[v][i] не перестанет быть предком $u$. Когда это произойдёт, подвинем указатель на $2^i$-го предка $v$ и продолжим дальше:

int lca(int v, int u) {
    if (a(v, u)) return v;
    if (a(u, v)) return u;
    for (int l = logn-1; l >= 0; l--)
        if (!ancestor(up[v][l], u))
            v = up[v][l];
    return up[v][0];
}

Указатель up[v][i] изначально является корнем дерева, а затем будет каждую итерацию спускаться на $2^i$. Когда он станет потомком lca, нам достаточно подняться всего лишь один раз, потому что два раза прыгнуть на расстояние $2^i$ это то же самое, что один раз прыгнуть на $2^{i+1}$, а мы могли это сделать на предыдущем шаге.

Ответ на произвольный запрос будет работать за $O(\log n)$, потому что мы фактически выполняем бинпоиск.

#Запросы на путях

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

Мы можем сделать такой же предподсчет, как в методе двоичных подъемов, но хранить вместе с номером $2^d$-ого предка минимум на соответствующем пути.

Заметим, что минимум на пути от $u$ до $v$ — это минимум от минимума на пути от $u$ до $lca(u, v)$ и от минимума на пути от $v$ до $lca(u, v)$. В свою очередь, оба этих минимума — это минимум на всех двоичных подъемах до LCA.

int get_min(int v, int u) {
    int res = inf;
    for (int l = logn-1; l >= 0; l--)
        if (!ancestor(up[v][l], u))
            v = up[v][l], res = min(res, mn[v][l]);
    for (int l = logn-1; l >= 0; l--)
        if (!ancestor(up[u][l], v))
            u = up[u][l], res = min(res, mn[u][l]);
    return min({res, mn[v][0], mn[u][0]})
}

Аналогичным образом можно считать сумму, gcd, полиномиальный хеш и много других странных функций на пути, но только в статическом случае — когда у нас нет обновлений. Для динамического случая существует гораздо более сложный метод, называемый heavy-light декомпозицией.