LCA (Binary Lifting)
O(log n) per queryLowest common ancestor with binary lifting: up[j][v] is the 2^j-th ancestor of v, built in O(n log n), queried in O(log n). Also gives k-th ancestor and tree distances. Built iteratively, so deep trees are safe.
// use it on
CSES: Company Queries II ↗
Answer q lowest-common-boss queries on an employee tree. Build once, answer each query with lca(u, v).
// the code
struct LCA {
int LOG;
vector<int> depth;
vector<vector<int>> up;
LCA(vector<vector<int>>& adj, int root = 0) {
int n = adj.size();
LOG = 1;
while ((1 << LOG) < n) LOG++;
depth.assign(n, 0);
vector<int> parent(n, root);
vector<bool> seen(n, false);
vector<int> st = {root}; // iterative DFS
seen[root] = true;
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int v : adj[u])
if (!seen[v]) {
seen[v] = true;
parent[v] = u;
depth[v] = depth[u] + 1;
st.push_back(v);
}
}
up.assign(LOG + 1, parent);
for (int j = 1; j <= LOG; j++)
for (int v = 0; v < n; v++)
up[j][v] = up[j - 1][up[j - 1][v]];
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int j = 0; diff; j++, diff >>= 1)
if (diff & 1) u = up[j][u];
if (u == v) return u;
for (int j = LOG; j >= 0; j--)
if (up[j][u] != up[j][v]) {
u = up[j][u];
v = up[j][v];
}
return up[0][u];
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
};