Watch 10 video solutions for Minimize the Total Price of the Trips, a hard level problem involving Array, Dynamic Programming, Tree. This walkthrough by A Code Daily! has 3,245 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Each node has an associated price. You are given an integer array price, where price[i] is the price of the ith node.
The price sum of a given path is the sum of the prices of all nodes lying on that path.
Additionally, you are given a 2D integer array trips, where trips[i] = [starti, endi] indicates that you start the ith trip from the node starti and travel to the node endi by any path you like.
Before performing your first trip, you can choose some non-adjacent nodes and halve the prices.
Return the minimum total price sum to perform all the given trips.
Example 1:
Input: n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]] Output: 23 Explanation: The diagram above denotes the tree after rooting it at node 2. The first part shows the initial tree and the second part shows the tree after choosing nodes 0, 2, and 3, and making their price half. For the 1st trip, we choose path [0,1,3]. The price sum of that path is 1 + 2 + 3 = 6. For the 2nd trip, we choose path [2,1]. The price sum of that path is 2 + 5 = 7. For the 3rd trip, we choose path [2,1,3]. The price sum of that path is 5 + 2 + 3 = 10. The total price sum of all trips is 6 + 7 + 10 = 23. It can be proven, that 23 is the minimum answer that we can achieve.
Example 2:
Input: n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]] Output: 1 Explanation: The diagram above denotes the tree after rooting it at node 0. The first part shows the initial tree and the second part shows the tree after choosing node 0, and making its price half. For the 1st trip, we choose path [0]. The price sum of that path is 1. The total price sum of all trips is 1. It can be proven, that 1 is the minimum answer that we can achieve.
Constraints:
1 <= n <= 50edges.length == n - 10 <= ai, bi <= n - 1edges represents a valid tree.price.length == nprice[i] is an even integer.1 <= price[i] <= 10001 <= trips.length <= 1000 <= starti, endi <= n - 1Problem Overview: You are given a tree with n nodes where each node has a price. Multiple trips occur between pairs of nodes, and the cost of a trip is the sum of prices along its path. Some nodes can have their price halved, but no two adjacent nodes can both be halved. The goal is to choose which nodes to discount so the total price across all trips is minimized.
Approach 1: DFS Traversal to Count Node Usage (Time: O(t * n), Space: O(n))
The first step is determining how many times each node contributes to the total cost. Build the tree using an adjacency list and run a DFS for every trip to find the path from source to destination. While backtracking, increment a frequency counter for each node on that path. After processing all trips, you know exactly how often each node's price is used in the total sum. The effective weight of a node becomes price[i] * freq[i]. This step relies on standard Depth-First Search traversal on a tree structure.
Approach 2: Dynamic Programming on Trees (Time: O(n), Space: O(n))
Once node frequencies are known, the problem becomes a tree version of the "House Robber" constraint: you cannot halve two adjacent nodes. Run another DFS with two states per node. dp0 represents the minimum cost if the current node is not discounted. dp1 represents the cost if the node is discounted (its contribution becomes (price[i] * freq[i]) / 2). If a node is discounted, none of its children can be discounted. During traversal, aggregate child costs accordingly: dp0 += min(child.dp0, child.dp1) and dp1 += child.dp0. This is classic Dynamic Programming on a graph that happens to be a tree. The final answer is min(root.dp0, root.dp1).
Recommended for interviews: Interviewers expect the tree DP solution. The DFS path counting step demonstrates you understand how to accumulate trip usage, while the dynamic programming phase shows mastery of tree state transitions. The optimal reasoning combines graph traversal with a two-state DP similar to House Robber on trees.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Traversal to Count Trip Paths | O(t * n) | O(n) | When constraints are small and you need to compute how often each node appears in trip paths |
| Dynamic Programming on Trees | O(n) | O(n) | General optimal solution for minimizing cost with adjacency constraints on tree nodes |