in a rooted tree, how to find the lowest common ancestor of two nodes?
linear #
we can do it in linear time. first move the deeper node to the same level as the another node. then move two nodes upward simultaneously until they meet.
def lca(u, v):
# to ensure u is always deeper
if depth[u] < depth[v]:
u, v = v, u
while depth[u] > depth[v]:
u = up[u][0]
while u != v:
u = up[u][0]
v = up[u][0]
return u
but if both the number of nodes 
and the number of queries 
is large (e.g. 
), we may use binary lifting to achieve faster result.
logarithmic #
we can move the deeper node to the same level as the another node using binary lifting.
then we want to move the two nodes upward at the same time. let’s try the power of 
from large to small (I know it is kind of random but this is maths). if they collide, they the node might be the LCA, might not be the LCA (then the LCA is below). if they do not collide, we must know that the LCA is above. hence we would like to jump only when they do not collide, otherwise we might jump over the LCA.
after the process, they must be the children of the LCA (since every integer have binary representation if that makes sense). therefore we can return the parent of either node.
note that we have to check if they are the same node after the initial jump, otherwise it would return the parent of LCA, which is the wrong answer.
a second note is the process is somehow similar to binary search. we are asking the question will the two nodes collide after they jump 
nodes upward and the answer for each is [False, ..., False, True, ..., True]. binary search is capable to find the intecepting point where the stream of False change to the stream of True. since the LCA is the first True, we can use binary search to do the job.
the time complexity is 
in the preprocessing and 
in the queires.
implementation #
def lca(u, v):
# to ensure u is always deeper
if depth[u] < depth[v]:
u, v = v, u
k = depth[u] - depth[v]
for j in range(LOG):
if ((k >> j) & 1):
u = up[u][j]
if u == v:
return u
for j in range(LOG)[::-1]:
if up[u][j] != up[v][j]:
u = up[u][j]
v = up[v][j]
return up[u][0]
related problems #
- CSES 1688 - Company Queries II
- CSES 1135 - Distance Queries
- Codeforces 1328E - Tree Queries
- Codeforces 1702G2 - Passable Paths (hard version)
- Codeforces 832D - Misha, Grisha and Underground