This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it.


Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the path lengths (i.e., sum of the weights along the unique path) between every pair requires $O(n^3)$ steps: there are $\binom{n}{2}$ pairs of vertices and we can always bound the number of edges on any path by $n-1$.


We can, however, do a great deal better with the following trick. Pick a root $r$ for $T$ arbitrarily. Define the least common ancestor of $i$ and $j$ as the vertex $a$ where the path from $i$ to $r$ meets the path from $j$ to $r$. Then if $d(\cdot,\cdot)$ denotes the distance in $T$, we get $d(i,j) = d(i,r) + d(j,r) - 2d(a,r)$. 


It's easy to see that all the $d(i,r)$ can be computed in $O(n)$ steps with BFS. There's also a data structure of [Harel and Tarjan](http://portal.acm.org/citation.cfm?id=373.411&coll=DL&dl=GUIDE&CFID=13201920&CFTOKEN=56615163) that, after $O(n)$ preprocessing will answer least common ancestor queries in $O(1)$ time. So the whole thing becomes $O(n^2)$.



All-pairs shortest paths in trees?
Just do a bfs on every node. Every search gives you a fine one-to-all shortest path in the tree.


All in all $n$ times $O(n)$ = $O(n^2)$.


You can also do it in $O(n)$, if you don't mind the distances being stored implicitly (still $O(1)$ lookups): Make an [LCA datastructure](https://en.wikipedia.org/wiki/Lowest_common_ancestor), and calculate the distances from the root to every node $d(u)$. Then the shortest path between $u$ and $v$ is just $d(u)+d(v)-2d(lca(u,v))$.


