I was thinking, since it is a tree, there is only one path between any two nodes. So applying shortest path algorithm (dijkstras) on each node and adding the distances will give the correct answer. But this approach is slow. All pairs of shortest path can be helpful here I think. But how do I implement it using adjacency list? It is a simple dp approach in adjacency matrix.
I also checked the solutions of others. They seem to use multiple DFS and BFS. What is their approach?
Computing all path lengths wont pass. Even if you could compute each in O(1) you still need O(n^2) just for summing them up.
I made two passes over the tree. In the first (bottom up) I computed the lengths of paths originating in the subtree below each vertex and ending in this vertex.
In the second (top down) I computed the missing paths (coming from above).
To be a little more precise:
At each node k we want to compute the number of nodes in the subtree with the current node as root n_k and the lengths of paths ending at the node from above (t_k) and from below (b_k).
First pass: At each vertex compute number of nodes from number of nodes of children.
The lengths of paths “from below” is given by the sum of the respective sum of pathlengths for the children plus the weight times the number of paths (since each path has to be extended by one edge). The number of paths is just the number of nodes below the current node
Second pass: Compute the sum of lengths of paths from above. Consider node i with parent j. Let b_k be the sum of pathlengths from below, t_k the same from above, n_k the number of nodes in the subtree with root k and w_{ij} the weight of the edge from node i to j. A small calculation yields: