title | authors | weight | prerequisites | ||
---|---|---|---|---|---|
Метод двоичных подъемов |
|
5 |
|
В контексте решения задачи LCA и не только популярен следующий метод.
Предподсчитаем для каждой вершины её 1-го предка, 2-го предка, 4-го и так далее. Сохраним их в двумерном массиве up
размера up[v][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;
}
Препроцессинг суммарно занимает up
, и каждый его элемент вычисляется за константу.
Пусть теперь поступил запрос нахождения LCA — пара вершин
- Проверим, не является ли одна вершина предком другой — в таком случае она и является результатом.
- Иначе, пользуясь массивом
up
, будем подниматься по предкам одной из них, пока не найдём самую высокую вершину, которая ещё не является предком другой. Следующая за ней будет искомым LCA.
Подробнее про второй пункт. Присвоим up[v][i]
не перестанет быть предком
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]
изначально является корнем дерева, а затем будет каждую итерацию спускаться на
Ответ на произвольный запрос будет работать за
Пусть нас вместо 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 декомпозицией.