Distance Between Two Nodes

The distance between u and v in a tree is dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]. Why?

The path connects u to v by going up to their LCA, then back down. The upward distance is depth[u] - depth[lca], and the downward distance is depth[v] - depth[lca]. Add them: (depth[u] - depth[lca]) + (depth[v] - depth[lca]) = depth[u] + depth[v] - 2 * depth[lca].

This formula works because trees have a unique path between any two nodes, and depth measures distance to the root. Once you have LCA and depths, computing distance is $O(1)$. This is why LCA is so useful for tree queries.