Distance query in trees with integer edge weights (Constant time, linear space) Consider an unrooted tree with integer edge weights. I'm looking for a linear space data structure which allows for constant time distance queries (finding the distance, i.e. the sum of edge weights, between any two vertices).

Is this possible? If yes, how? I have an idea that it should be possible using some Lowest-Common-Ancestor or Range-Minimum-Query approach.
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.