Can be solved using two DFS calls and tree rerooting in O(N) while maintaining a DP array where DP[node] = sum for all paths from node to all the nodes in its subtree (considering 1 as the initial root). Tree rerooting can be used to calculate the sum for all nodes.

It's easier to solve by counting in how many paths each edge participates which is v*(n-v) if 'v' is number of nodes in its subtree. So just BFS is enough to get topological order to calc these amounts.