Skip to main content
Talentd

Minimize the Total Price of the Trips - Solution & Explanation

HardArrayDynamic ProgrammingTreeDepth-First Search16 min read
Practice this problem

Problem Statement

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 <= 50
  • edges.length == n - 1
  • 0 <= ai, bi <= n - 1
  • edges represents a valid tree.
  • price.length == n
  • price[i] is an even integer.
  • 1 <= price[i] <= 1000
  • 1 <= trips.length <= 100
  • 0 <= starti, endi <= n - 1

Approach Overview

Problem 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 1: Depth-First Search (DFS) Traversal

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming on Trees

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Enumeration

We can enumerate each element div in divisors, and calculate how many elements in nums can be divided by div, denoted as cnt.

  • If cnt is greater than the current maximum divisibility score mx, then update mx = cnt, and update ans = div.
  • If 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n), due to the recursion stack and the graph representation.

Dynamic Programming on Trees

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.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Traversal to Count Trip PathsO(t * n)O(n)When constraints are small and you need to compute how often each node appears in trip paths
Dynamic Programming on TreesO(n)O(n)General optimal solution for minimizing cost with adjacency constraints on tree nodes

Video Solution

Minimize the Total Price of the Trips | Leetcode Contest 341 • A Code Daily! • 3,261 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimize the Total Price of the Trips easy or hard?
Minimize the Total Price of the Trips is classified as a Hard problem on LeetCode. The difficulty comes from combining two ideas: counting node usage across multiple paths in a tree and applying a two-state dynamic programming strategy similar to House Robber on trees.
Minimize the Total Price of the Trips Python/Java solution
Typical implementations use DFS to find each trip path and count node frequencies, followed by a tree DP. Python solutions rely on recursion and adjacency lists, while Java versions maintain two DP states per node inside a recursive traversal. Both implementations run in O(t * n) preprocessing and O(n) DP time.
How to solve Minimize the Total Price of the Trips in O(n)?
The optimization step itself runs in O(n) using tree dynamic programming. After computing node visit frequencies, perform a DFS where each node maintains two states: cost without discount and cost with discount. Children cannot be discounted if the parent is discounted, producing a classic two-state tree DP.
What is the best approach for Minimize the Total Price of the Trips?
The optimal approach combines DFS path counting with dynamic programming on trees. First count how many times each node appears in all trip paths using DFS. Then run a tree DP with two states per node (discounted or not discounted) while enforcing that adjacent nodes cannot both be discounted. The DP runs in O(n) after preprocessing.
Is Minimize the Total Price of the Trips asked at Google/Amazon/Meta?
Tree dynamic programming and path aggregation problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variants of the House Robber on trees or graph traversal combined with DP are common interview patterns.
What data structure is used in Minimize the Total Price of the Trips?
The main data structure is an adjacency list representing the tree. Depth-first search traverses the graph to compute trip paths and perform the DP transitions. Arrays store node prices, frequency counts, and DP states for each node.
What is the time complexity of Minimize the Total Price of the Trips?
The overall time complexity is O(t * n + n), where t is the number of trips and n is the number of nodes. DFS is executed once per trip to determine the nodes on each path, and a second DFS performs the dynamic programming over the tree. Space complexity is O(n) for adjacency lists, recursion stack, and DP states.

Ready to solve this problem?

Practice Minimize the Total Price of the Trips with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays