forked from t3nsor/codebook
-
Notifications
You must be signed in to change notification settings - Fork 0
/
lca.cpp
74 lines (52 loc) · 1.19 KB
/
lca.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; ++i)
constexpr int MAX = 1e5 + 1;
constexpr int LGMAX = 18;
std::vector<int> adjList[MAX];
int visited[MAX], depths[MAX];
int parent[MAX][LGMAX];
int depth;
int n; // number of nodes
void dfs (int u)
{
visited[u] = true;
depths[u] = ++depth;
for (auto& v : adjList[u])
if (!visited[v]) {
parent[v][0] = u;
dfs (v);
}
--depth;
}
void setup (void)
{
rep (i, 1, LGMAX - 1)
rep (j, 1, n) {
int p = parent[j][i - 1];
if (p)
parent[j][i] = parent[p][i - 1];
}
}
int lca (int x, int y)
{
int diff = depths[x] - depths[y];
if (diff < 0) {
diff *= -1;
std::swap (x, y);
}
int i = 0;
while (diff) {
if (diff & 1)
x = parent[x][i];
++i;
depth >>= 1;
}
if (x == y)
return x;
for (int i = LGMAX - 1; i >= 0; --i)
if (parent[x][i] != parent[y][i]) {
x = parent[x][i];
y = parent[y][i];
}
return parent[x][0];
}