LCA (Lowest Common Ancestor) - YessineJallouli/Competitive-Programming GitHub Wiki
#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;
const int N = 3e5+7;
const int LOG = 20;
int up[N][LOG];
int depth[N];
vector<vector<int>> tree(N);
void dfs(int a) {
for (int b : tree[a]) {
depth[b] = depth[a]+1;
up[b][0] = a;
for (int j = 1; j < LOG; j++)
up[b][j] = up[up[b][j-1]][j-1];
dfs(b);
}
}
int LCA(int a, int b) {
if (depth[b] > depth[a])
swap(a,b);
int k = depth[a]-depth[b];
for (int j = LOG-1; j >= 0; j--) {
if (k & (1 << j))
a = up[a][j];
}
if (a == b)
return a;
for (int j = LOG-1; j >= 0; j--) {
if (up[a][j] != up[b][j]) {
a = up[a][j];
b = up[b][j];
}
}
return up[a][0];
}
int main() {
SaveTime
}
Resources :
https://youtu.be/oib-XsjFa-M
https://youtu.be/dOAxrhAUIhA
Problems :
https://codeforces.com/gym/101473/attachments (Problem J)