-
Notifications
You must be signed in to change notification settings - Fork 0
/
LCA.cpp
38 lines (34 loc) · 932 Bytes
/
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
vector<bool> vis(n + 2, 0);
vector<vector<int>> sparse(n + 2, vector<int>(19, 0));
vector<int> depth(n + 2, 0);
function<void(int, int)> dfs = [&](int node, int p) -> void {
vis[node] = 1;
sparse[node][0] = p;
for (int i = 1; i < 19; i++) {
sparse[node][i] = (sparse[node][i - 1] >= 0 ? sparse[sparse[node][i - 1]][i - 1] : -1);
}
for (auto i : adj[node]) {
if (!vis[i]) {
depth[i] = depth[node] + 1;
dfs(i, node);
}
}
};
auto LCA = [&](int u, int v) -> int {
if (depth[u] < depth[v])
swap(u, v);
for (int i = 18; i >= 0; i--) {
if (depth[v] + (1 << i) <= depth[u]) {
u = sparse[u][i];
}
}
if (u == v)
return u;
for (int i = 18; i >= 0; i--) {
if (sparse[u][i] != sparse[v][i]) {
u = sparse[u][i];
v = sparse[v][i];
}
}
return sparse[u][0];
};