Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
