Двоичные подъемы

Материал из Algocode wiki
Версия от 15:55, 15 февраля 2020; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Наивное решение

Давайте найдем массив предков для всех вершин - $p$(сделать это не сложно, давайте просто в DFS-е помечать из какой вершины мы пришли, тогда как найти $lca(u, v)$, Давайте просто подниматься по предкам $u$ пока не дойдем до вершины которая является одновременно и предком $v$. К сожалению это работает за $O(n)$ на запрос.

Идея

Нам как-то бы хотелось получать не просто предка вершины, но и $i$-ого предка вершины.

Подход

Давайте сделаем массив $p_{i, j}$ - предок вершины $i$ на расстоянии $j$, теперь на запрос $lca(u, v)$ мы можем сделать бинпоиск по расстоянию до $lca(u, v)$ от вершины $u$, теперь мы умеем отвечать на запрос за $O(log(n))$, но подсчет предков работает за $O(n^2)$

Давайте теперь скажем, что $p_{i, j}$ - предок вершины $i$ на расстоянии $2^{j}$, так как любое число можно представить в виде суммы степеней двойки, то давайте делать следующее, проверим, что вершина $p(u, 2^j)$ является предком $v$, если это так, то просто посмотрим на следующую степень двойки, то есть скажем, что $j = j - 1$, если же она не является предком, то скажем, что $u = p(u, 2^j), j = j - 1$

Утверждение

Таким способам мы получим сына вершины $lca(u, v)$, так как мы каждый раз просто берем предка вершины $u$, который не является предком $v$

Код

 1 int n;
 2 const int N = 1e5, C = 20; // N - max size tree, 2^C > N
 3 vector<int> g[N];
 4 int tin[N], tout[N];
 5 int timer;
 6 int up[N][C];
 7 
 8 void dfs (int v, int p = 0) {
 9      tin[v] = ++timer;
10      up[v][0] = p;
11      for (int i = 1; i <= l; I++) {
12           up[v][i] = up[up[v][i - 1]][i - 1];
13      }
14      for (int i = 0; i < g[v].size(); i++) {
15           int to = g[v][i];
16           if (to != p) {
17                dfs(to, v);
18           }
19      }
20      tout[v] = ++timer;
21 }
22 
23 bool upper (int a, int b) {
24      return tin[a] <= tin[b] && tout[a] >= tout[b];
25 }
26 
27 int lca (int a, int b) {
28 	if (upper(a, b)) {
29                 return a;
30         }
31 	if (upper(b, a)) {
32                 return b;
33         }
34 	for (int i = C - 1; i >= 0; i--) {
35 		if (!upper(up[a][i], b)) {
36 			a = up[a][i];
37                 }
38         }
39  	return up[a][0];
40 }
41 
42 int main() {
43 	dfs(0);
44         int a, b;
45 	while(cin >> a >> b) {
46 		cout << lca(a, b) << "\n";
47 	}
48 
49 }



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin