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.
Depth-First Search (DFS) is an effective method for traversing trees and graphs, which can help calculate the price sums over paths efficiently. In this method, the tree is traversed using DFS from each start node to the end node of each trip. The path is traversed by performing a DFS from the root node and accumulating the price at each node until reaching the end node of a trip.
The solution first constructs a graph representation of the tree using adjacency lists. A DFS function is defined to find paths from the start to end nodes. For each specified trip in the input, DFS is run to find the path, from which price sums are calculated and divided by two (simulating halving prices). The key detail is using a visited set to prevent revisiting nodes, ensuring non-adjacent nodes have their prices halved where possible.
Time Complexity: O(n * t), where n is the number of nodes and t is the number of trips, because DFS will run once for every trip.
Space Complexity: O(n), due to the recursion stack and the graph representation.
Dynamic Programming on Trees is a strategy where you traverse the tree with dynamic programming techniques in mind, to keep track of possible price reductions on paths. This approach benefits from storing results for subproblems that can be reused later.
The solution employs dynamic programming to compute the minimum price for each node both with full and half prices. The DFS function is used to populate the dpFull and dpHalf arrays as it traverses the tree. The result is built by considering already computed results of children nodes, thus efficiently halving the price at non-adjacent nodes for minimizing the price sums required on the trips.
Java
JavaScript
Time Complexity: O(n), as each node and edge is visited once in the DFS traversal.
Space Complexity: O(n), for the DP arrays and graph structure.
We can enumerate each element div in divisors, and calculate how many elements in nums can be divided by div, denoted as cnt.
cnt is greater than the current maximum divisibility score mx, then update mx = cnt, and update ans = div.cnt equals mx and div is less than ans, then update ans = div.Finally, return ans.
The time complexity is O(m times n), where m and n are the lengths of nums and divisors respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Traversal | Time Complexity: O(n * t), where n is the number of nodes and t is the number of trips, because DFS will run once for every trip. |
| Dynamic Programming on Trees | Time Complexity: O(n), as each node and edge is visited once in the DFS traversal. |
| Enumeration | — |
| 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 |
Minimize the Total Price of the Trips | Leetcode Contest 341 • A Code Daily! • 3,245 views views
Watch 9 more video solutions →Practice Minimize the Total Price of the Trips with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor