LeetCode Solutions Blog

Minimize the Total Price of the Trips

Number: 2739

Difficulty: Hard

Paid? No

Problem Description

Given an undirected tree with n nodes (indexed 0 to n-1) and n-1 edges, each node has a given price. You are also provided several trips defined by their start and end nodes. You can choose a set of non-adjacent nodes (before making any trip) and halve their price. The cost of a trip is the sum of the prices on the path taken. The goal is to pick the nodes to discount so that the total cost of all trips is minimized.

Key Insights

Count the number of times each node is used on any trip. As the tree is undirected and unique paths exist between any two nodes, a DFS/BFS can be used per trip.
Convert the problem into one of maximizing the savings: For a node, if its cost is halved, the saving is half of its price multiplied by the number of times it appears. The total trip cost becomes (total cost without discounts) minus the total “saving.”
Because one can only discount non-adjacent nodes, the problem reduces to a tree dynamic programming (DP) formulation on the tree with two states per node: discounted (chosen) or not.
Use a DFS-based DP on the tree (rooting the tree arbitrarily) where: • If a node is discounted, its children cannot be discounted. • Otherwise, each child may be either discounted or not based on which yields maximum saving.
Final answer = total trip cost without discount − maximum total saving calculated by the DP.

Space and Time Complexity

Time Complexity: O(t * n + n), where t is the number of trips (since each trip may require a DFS to record the unique path) and n is the number of nodes (for the DP traversal).
Space Complexity: O(n + t) due to storing the tree adjacency list, count array, and recursion stack.

Solution

The solution first records how many times each node is visited by processing each trip with a DFS that finds the unique path from start to end. Once the frequency counts are available, the “saving” for discounting a node is count[node]*(price[node]//2). Next, an arbitrary root is chosen to run a DFS-based tree DP where for each node, two values are computed:

savings if the node is not discounted: sum of maximum savings obtainable by children (they may or may not be discounted).
savings if the node is discounted: saving from the current node plus savings from children when none of them is discounted. Finally, subtract the maximum saving (obtained from the root’s DP) from the total cost (computed with the original prices and counts) to get the minimized cost.

Code Solutions

# Python solution with line-by-line comments

from collections import defaultdict, deque

class Solution:
    def minimumTotalPrice(self, n: int, edges: list, price: list, trips: list) -> int:
        # Build tree adjacency list from edges
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)
        
        # Count appearance of each node from all trips
        count = [0] * n
        
        # Helper: DFS to find path from start to end and update count for nodes in that path.        
        def findPath(start, end):
            # Use DFS recursion and return path if found, else None
            stack = [(start, [start])]
            seen = set([start])
            while stack:
                node, path = stack.pop()
                if node == end:
                    return path
                for neighbor in tree[node]:
                    if neighbor not in seen:
                        seen.add(neighbor)
                        stack.append((neighbor, path + [neighbor]))
            return []
        
        # Process each trip and update the visit count for each node in the found path
        for start, end in trips:
            path = findPath(start, end)
            for node in path:
                count[node] += 1
        
        # Total cost without any discounts.
        total_cost = sum(count[i] * price[i] for i in range(n))
        
        # DP: for each node, return a tuple (notDiscounted, discounted)
        # where:
        # - notDiscounted: maximum saving without discounting the current node
        # - discounted: maximum saving with discount applied to current node.
        #
        # discount saving for the node is count[node] * (price[node] // 2)
        def dfs(u, parent):
            notDiscounted = 0  # if not discounting u, children can be either
            discounted = count[u] * (price[u] // 2)  # discounting u, saving for u
            
            # Process all children of u (neighbors that are not the parent)
            for child in tree[u]:
                if child == parent:
                    continue
                # Recursively get savings from child
                child_not, child_discounted = dfs(child, u)
                # If u is not discounted, child may choose maximum saving whether discounted or not.
                notDiscounted += max(child_not, child_discounted)
                # If u is discounted, then child MUST NOT be discounted (to remain non-adjacent)
                discounted += child_not
            return (notDiscounted, discounted)
        
        # Run DFS from an arbitrary root (here 0). Since the DP properly handles tree structure,
        # it covers all nodes.
        res_not, res_discounted = dfs(0, -1)
        max_savings = max(res_not, res_discounted)
        
        # Return minimized total trip cost = total cost (without discount) - maximum savings
        return total_cost - max_savings

# Example usage:
# sol = Solution()
# print(sol.minimumTotalPrice(4, [[0,1],[1,2],[1,3]], [2,2,10,6], [[0,3],[2,1],[2,3]]))