O(n+m) solution exists: extend <https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm> to keep not only the top of each set in the disjoint-set forest, but also the weight of the path till that top.

is it doing search in O(1) for each pair of nodes?