Lowest Common Ancestor
Binary lifting (better way)
Section titled “Binary lifting (better way)”const int N = 1e6 + 5;const int LOG_N = 20 + 1;
int in[N], ou[N], TIME = 0;int up[N][LOG_N];vector<int> g[N];
void dfs(int u, int p) { in[u] = ++TIME; up[u][0] = p; for (int i = 1; i < LOG_N; ++i) { up[u][i] = up[up[u][i - 1]][i - 1]; } for (auto &v : g[u]) { if (v == p) continue; dfs(v, u); } ou[u] = ++TIME;}
int lca(int u, int v) { auto is_ancestor = [&](int u, int v) { return in[u] <= in[v] && ou[v] <= ou[u]; }; if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (int i = LOG_N - 1; i >= 0; --i) { if (!is_ancestor(up[u][i], v)) { u = up[u][i]; } } return up[u][0];}
inline void solve() { int n; cin >> n; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 1);
// Verification for (int i = 1; i <= n; ++i) { for (int j = 1; j < i; ++j) { cout << j << ' ' << i << ' ' << lca(i, j) << '\n'; } }}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; for (int i = 1; i <= t; ++i) { solve(); }}
Brute Force
Section titled “Brute Force”const int N = 5e5 + 5;vector<int> g[N];int p[N], h[N];
void dfs(int u, int pa = -1) { p[u] = pa; if (pa != -1) { h[u] = h[pa] + 1; } for (auto &v : g[u]) if (v != pa) dfs(v, u);}
int lca(int u, int v) { if (u == v) return u; if (h[u] < h[v]) swap(u, v); return lca(p[u], v);}
void solve() { int n, q; cin >> n >> q; for (int i = 0; i < n; ++i) { g[i].clear(); h[i] = 0; } for (int i = 1; i < n; ++i) { int p; cin >> p; g[p].push_back(i); } dfs(0); while (q--) { int u, v; cin >> u >> v; cout << lca(u, v) << '\n'; }}
Binary Lifting
Section titled “Binary Lifting”const int N = 5e5 + 5;const int LOG_N = 19; /* added */vector<int> g[N];// int p[N], h[N];int p[N][LOG_N], h[N];
void dfs(int u, int pa = -1) { p[u][0] = pa; /* diff */ if (pa != -1) { h[u] = h[pa] + 1; } for (int i = 1; i < LOG_N; ++i) /* added */ if (p[u][i - 1] != -1) p[u][i] = p[p[u][i - 1]][i - 1]; /* added */ for (auto &v : g[u]) if (v != pa) dfs(v, u);}
int lca(int u, int v) { if (h[u] < h[v]) swap(u, v); for (int i = LOG_N - 1; i >= 0; --i) /* added */ if (p[u][i] != -1 && h[p[u][i]] >= h[v]) u = p[u][i]; if (u == v) return u; /* moved */ for (int i = LOG_N - 1; i >= 0; --i) /* added */ if (p[u][i] != p[v][i]) { u = p[u][i]; v = p[v][i]; } return p[u][0]; /* diff */}
void solve() { int n, q; cin >> n >> q; for (int i = 0; i < n; ++i) { g[i].clear(); h[i] = 0; for (int j = 0, k = 1; k < n; ++j, k <<= 1) p[i][j] = -1; } /* added */ for (int i = 1; i < n; ++i) { int p; cin >> p; g[p].push_back(i); } dfs(0); while (q--) { int u, v; cin >> u >> v; cout << lca(u, v) << '\n'; }}