Двоичные подъемы: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «==Наивное решение== Давайте найдем массив предков для всех вершин - $p$(сделать это не слож...») |
Глеб (обсуждение | вклад) |
||
Строка 15: | Строка 15: | ||
==Утверждение== | ==Утверждение== | ||
− | Таким способам мы получим сына вершины $lca(u, v)$, так как мы каждый раз просто берем предка вершины | + | Таким способам мы получим сына вершины $lca(u, v)$, так как мы каждый раз просто берем предка вершины $u$, который не является предком $v$ |
==Код== | ==Код== |
Версия 11:05, 27 ноября 2019
Содержание
Наивное решение
Давайте найдем массив предков для всех вершин - $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