The lowest common ancestor of u and v is the deepest node that lies on both paths to the root. Naive: walk parents until you meet — O(n) per query, dead at n, q = 2·10⁵.
Binary lifting: up[0][v] = parent[v], up[k][v] = up[k-1][up[k-1][v]]. To lift v by d steps, walk the bits of d. LCA: lift the deeper node to the same depth, then lift both while their next 2^k ancestors differ.
CSES Company Queries II / Distance Queries (dist(u,v) = depth[u]+depth[v]-2·depth[lca]). USACO Gold lists this under optional Euler-tour LCA too — RMQ on the Euler tour is equivalent; lifting is the one you type first.
function buildLca(n, parent, depth) {
const LOG = Math.ceil(Math.log2(n)) + 1;
const up = Array.from({ length: LOG }, () => Array(n).fill(0));
up[0] = parent.slice();
for (let k = 1; k < LOG; k++) {
for (let v = 0; v < n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
}
function lift(v, dist) {
for (let k = 0; dist > 0; k++, dist >>= 1) if (dist & 1) v = up[k][v];
return v;
}
function lca(u, v) {
if (depth[u] < depth[v]) [u, v] = [v, u];
u = lift(u, depth[u] - depth[v]);
if (u === v) return u;
for (let k = LOG - 1; k >= 0; k--) {
if (up[k][u] !== up[k][v]) {
u = up[k][u];
v = up[k][v];
}
}
return up[0][u];
}
return { lca, lift };
}Checks 0/2