Core Idea - Precompute Depths and LCA

Run DFS to compute depth[v] for each node. Build the binary lifting table or Euler tour + sparse table for fast LCA queries. With these precomputed structures, each distance query becomes a simple formula: depth[u] + depth[v] - $2$ * depth[lca(u, v)]. The preprocessing cost ($O(n \log n))$ is paid once, then you answer many queries efficiently.

This is a classic space-time tradeoff: spend more memory and preprocessing time to get faster queries. The same pattern appears in many tree problems: precompute structural information (depths, ancestors, subtree sizes), then use it to answer queries quickly.