Distances at Scale — Solution & Editorial

Back to the Problem

dist(a, b) = depth(a) + depth(b) − 2·depth(LCA). Binary-lifting LCA answers each query in O(log N); per-query BFS is O(NQ) and dies.

Complexity: O((N + Q) log N)