Distance query in trees with integer edge weights (Constant time, linear space)
Pick an arbitrary node to be the root.  Store in each node its depth (distance from the root).  Also, build a least-common ancestor data structure so you can answer least-common ancestor queries in constant time.

Given two vertices $u,v$, compute their least common ancestor, $a$.  Now the shortest path from $u$ to $v$ goes up from $u$ to $a$, then down to $v$.  You can compute the length of this path as

$$(\text{depth}(u)-\text{depth}(a)) + (\text{depth}(v) - \text{depth}(a)).$$

That's the distance from $u$ to $v$.  Total running time is $O(1)$ time per query.  There exist LCA data structures that use only linear space.