Наименьший общий предок. Нахождение за O (log N) (метод двоичного подъёма)

Пусть дано дерево G. На вход поступают запросы вида (V1, V2), для каждого запроса требуется найти их наименьшего общего предка, т.е. вершину V, которая лежит на пути от корня до V1, на пути от корня до V2, и из всех таких вершин следует выбирать самую нижнюю. Иными словами, искомая вершина V - предок и V1, и V2, и среди всех таких общих предков выбирается нижний. Очевидно, что наименьший общий предок вершин V1 и V2 - это их общий предок, лежащий на кратчайшем пути из V1 в V2. В частности, например, если V1 является предком V2, то V1 является их наименьшим общим предком.

На английском эта задача называется задачей LCA - Least Common Ancestor.

Здесь будет рассмотрен алгоритм, который пишется намного быстрее, чем описанный здесь.

Асимптотика полученного алгоритма будет равна: препроцессинг за O (N log N) и ответ на каждый запрос за O (log N).

Алгоритм

Предпосчитаем для каждой вершины её 1-го предка, 2-го предка, 4-го, и т.д. Обозначим этот массив через P, т.е. P[i][j] - это 2^j-й предок вершины i, i = 1..N, j = 0..⌈logN⌉. Также для каждой вершины найдём времена захода в неё и выхода поиска в глубину (см. "Поиск в глубину") - это нам понадобится, чтобы определять за O (1), является ли одна вершина предком другой (не обязательно непосредственным). Такой препроцессинг можно выполнить за O (N log N).

Пусть теперь поступил очередной запрос - пара вершин (A,B). Сразу проверим, не является ли одна вершина предком другой - в таком случае она и является результатом. Если A не предок B, и B не предок A, то будем подниматься по предкам A, пока не найдём самую высокую (т.е. наиболее близкую к корню) вершину, которая ещё не является предком (не обязательно непосредственным) B (т.е. такую вершину X, что X не предок B, а P[X][0] - предок B). При этом находить эту вершину X будем за O (log N), пользуясь массивом P.

Опишем этот процесс подробнее. Пусть L = ⌈logN⌉. Пусть сначала I = L. Если P[A][I] не является предком B, то присваиваем A = P[A][I], и уменьшаем I. Если же P[A][I] является предком B, то просто уменьшаем I. Очевидно, что когда I станет меньше нуля, вершина A как раз и будет являться искомой вершиной - т.е. такой, что A не предок B, но P[A][0] - предок B.

Теперь, очевидно, ответом на LCA будет являться P[A][0] - т.е. наименьшая вершина среди предков исходной вершины A, являющаяся также и предком B.

Асимптотика. Весь алгоритм ответа на запрос состоит из изменения I от L = ⌈logN⌉ до 0, а также проверки на каждом шаге за O(1), является ли одна вершина предком другой. Следовательно, на каждый запрос будет найден ответ за O (log N).

Реализация

int n, l;
vector < vector<int> > g;
vector<int> tin, tout;
int timer;
vector < vector<int> > up;

void dfs (int v, int p = 0) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i=1; i<=l; ++i)
		up[v][i] = up[up[v][i-1]][i-1];
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (to != p)
			dfs (to, v);
	}
	tout[v] = ++timer;
}

bool upper (int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca (int a, int b) {
	if (upper (a, b))  return a;
	if (upper (b, a))  return b;
	for (int i=l; i>=0; --i)
		if (! upper (up[a][i], b))
			a = up[a][i];
	return up[a][0];
}

int main() {

	... чтение n и g ...

	tin.resize (n),  tout.resize (n),  up.resize (n);
	l = 1;
	while ((1<<l) <= n)  ++l;
	for (int i=0; i<n; ++i)  up[i].resize (l+1);
	dfs (0);

	for (;;) {
		int a, b; // текущий запрос
		int res = lca (a, b); // ответ на запрос
	}

}