Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
The final answer is the price[i] * freq[i], where freq[i] is the number of times node i was visited during the trip, and price[i] is the final price.
To find freq[i] we will use dfs or bfs for each trip and update every node on the path start and end.
Finally, to find the final price[i] we will use dynamic programming on the tree. Let dp(v, 0/1) denote the minimum total price with the node v’s price being halved or not.