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.