Problem - Distance Queries

You are given a tree with $n$ nodes and $q$ queries. Each query asks for the distance between two nodes. Since $q$ can be large (up to $200,000$), you want $O(1)$ queries. Use Euler tour + sparse table for LCA, then apply the distance formula. Preprocess: run DFS to compute depths, build Euler tour, build sparse table.

For each query (u, v), find lca(u, v) in $O(1)$, then compute depth[u] + depth[v] - 2 * depth[lca] in $O(1)$. Total time: $O(n \log n + q)$. This is fast enough for the problem constraints. The insight is recognizing that distance queries reduce to LCA queries.