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.