Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T_k$ has a vertex $k$ connected to $R$ in $T$.
Now there are 3 types of paths contributing to the sum of cost of paths $N(R)$:
- $I(R)$, the cost of all inner paths of the sub-trees (computed with recursion),
- $S(R)$, the cost of all paths starting on $R$: $(R, i)$ for any $i \ne R$,
- $C(R)$, the paths between the different sub-trees.
Once you recursively have computed the 3 components for each of these vertex $k$ in its own sub-tree $T_k$. Let's call $E(k, R)$ the cost of the edge $(k, R)$ and $n_k$, the number of vertices in $T_k$.
You can compute $N(R)$:
- $I(R) = \sum_k N(k)$
- $S(R) = \sum_k S(k)+n_k E(k, R)$,
- $C(R) = \sum_{k1, k2, k1 \ne k2}(S(k1)+n_{k1}E(k1, R))(S(k2)+n_{k2}E(k2, R))$
Note that if $R$ is connected to only one other vertex, $C(R) = 0$. You also can track $n$ with $n_R = \sum_k n_k + 1$.
This has a linear time and space complexity.