{"id":"dsa/lca-binary-lifting#order-1l6usfx","promptHtml":"Arrange the LCA function.","lang":"cpp","lines":[{"text":"int lca(int u, int v) {","html":"int lca(int u, int v) {"},{"text":" if (depth_[u] < depth_[v]) swap(u, v);","html":" if (depth_[u] < depth_[v]) swap(u, v);"},{"text":" u = kth(u, depth_[u] - depth_[v]);","html":" u = kth(u, depth_[u] - depth_[v]);"},{"text":" if (u == v) return u;","html":" if (u == v) return u;"},{"text":" for (int j = LOG - 1; j >= 0; j--)","html":" for (int j = LOG - 1; j >= 0; j--)"},{"text":" if (up[j][u] != up[j][v]) { u = up[j][u]; v = up[j][v]; }","html":" if (up[j][u] != up[j][v]) { u = up[j][u]; v = up[j][v]; }"},{"text":" return up[0][u];","html":" return up[0][u];"},{"text":"}","html":"}"}],"distractors":[{"text":" for (int j = 0; j < LOG; j++)","html":" for (int j = 0; j < LOG; j++)"},{"text":" return u;","html":" return u;"}],"whyHtml":"Equalise depths first. Then try the biggest jump first and take it only if the ancestors differ, so both nodes stay just below the LCA. The answer is their common parent."}