LeetCode 2646 - Minimize the Total Price of the Trips

The problem gives us an undirected tree with n nodes. Every node has a price associated with it, and we are also given several trips between pairs of nodes. Since the graph is a tree, there is exactly one simple path between any two nodes.

leetcodehardarraydynamic-programmingtreedepth-first-searchgraph-theory

LeetCode Problem 2646

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Tree, Depth-First Search, Graph Theory

Solution

Problem Understanding

The problem gives us an undirected tree with n nodes. Every node has a price associated with it, and we are also given several trips between pairs of nodes. Since the graph is a tree, there is exactly one simple path between any two nodes.

For every trip, we travel along the unique path between the starting node and the ending node. The total cost of that trip is the sum of the prices of all nodes on that path.

Before any trips begin, we are allowed to choose some nodes and halve their prices. However, there is one important restriction: no two chosen nodes can be adjacent in the tree. This transforms the problem into a tree optimization problem involving independent node selection.

Our goal is to minimize the total cost across all trips.

The input consists of:

  • n, the number of nodes
  • edges, describing the tree structure
  • price, where price[i] is the price of node i
  • trips, where each trip specifies a start and end node

The output is the minimum total price after optimally selecting which non-adjacent nodes should have their prices halved.

The constraints are relatively small:

  • n <= 50
  • trips.length <= 100

These constraints are important because they allow us to perform DFS traversals repeatedly without performance concerns. A solution with complexity around O(n^2) or O(n^3) is completely acceptable.

There are several important observations and edge cases:

  • Because the graph is a tree, there is exactly one path between any two nodes.
  • A node may appear in many trips, so halving a frequently used node can produce large savings.
  • The adjacency restriction means we cannot greedily halve every expensive node.
  • Trips may start and end at the same node, producing a path of length one.
  • Since all prices are even integers, halving always produces an integer value.

The key challenge is balancing global savings while respecting the non-adjacent constraint.

Approaches

Brute Force Approach

The brute force solution tries every possible subset of nodes that satisfies the non-adjacent condition.

For each valid subset:

  1. Halve the selected node prices.
  2. Compute the cost of every trip.
  3. Sum all trip costs.
  4. Track the minimum total.

To check whether a subset is valid, we ensure no edge connects two selected nodes.

To compute trip costs, we can run DFS to find the unique path for each trip.

This approach is correct because it exhaustively explores all legal node selections. Eventually, it will evaluate the optimal configuration.

However, it is far too slow. There are 2^n subsets of nodes. Even though n = 50 is small for polynomial algorithms, it is enormous for exponential enumeration.

Optimal Approach

The important insight is that the trips only matter through how many times each node is used.

Suppose node i appears in all trip paths freq[i] times. Then:

  • Without halving, node i contributes:

freq[i] * price[i]

  • With halving, node i contributes:

freq[i] * (price[i] / 2)

So the problem becomes:

Choose a set of non-adjacent nodes to maximize total savings.

This is a classic tree dynamic programming problem, specifically the "maximum weighted independent set on a tree" pattern.

We first compute how many times each node appears across all trip paths. Then we perform tree DP:

  • dp[node][0] = minimum cost if this node is NOT halved
  • dp[node][1] = minimum cost if this node IS halved

If a node is halved, none of its children may be halved.

This converts the problem into a clean DFS dynamic programming solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n × n × trips) O(n) Enumerates all valid subsets
Optimal O(n × trips + n) O(n) Counts node frequencies, then performs tree DP

Algorithm Walkthrough

Step 1: Build the adjacency list

Since the input graph is a tree, we represent it using an adjacency list.

This allows efficient DFS traversal between connected nodes.

Step 2: Count how many times each node is used

We create an array:

frequency[i]

This stores how many trips pass through node i.

For every trip:

  1. Run DFS from start to end
  2. Recover the unique path
  3. Increment the frequency of every node on that path

Because the graph is a tree, DFS always finds exactly one valid simple path.

Step 3: Convert node usage into total contribution

Once frequencies are known:

  • Normal cost of node:

frequency[node] * price[node]

  • Halved cost:

frequency[node] * price[node] // 2

Now the trips themselves no longer matter. We only care about minimizing total node contribution.

Step 4: Root the tree

We root the tree arbitrarily at node 0.

This allows us to perform parent-child DP transitions cleanly.

Step 5: Perform tree DP

For every node, compute two states:

  • not_halved
  • halved

If current node is not halved:

  • Children may either be halved or not halved
  • Take minimum of both states for each child

If current node is halved:

  • Children cannot be halved
  • Only use child not_halved state

Step 6: Return the minimum

At the root:

min(not_halved, halved)

This is the globally optimal answer.

Why it works

The algorithm works because the total trip cost can be decomposed into independent node contributions.

After counting node frequencies, each node contributes a fixed amount depending only on whether it is halved. The only interaction between nodes is the adjacency restriction.

This transforms the problem into selecting a minimum-cost configuration on a tree with parent-child constraints, which is exactly what tree DP solves optimally.

Python Solution

from typing import List

class Solution:
    def minimumTotalPrice(
        self,
        n: int,
        edges: List[List[int]],
        price: List[int],
        trips: List[List[int]]
    ) -> int:
        
        graph = [[] for _ in range(n)]
        
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        frequency = [0] * n
        
        def find_path(node: int, parent: int, target: int, path: List[int]) -> bool:
            path.append(node)
            
            if node == target:
                return True
            
            for neighbor in graph[node]:
                if neighbor == parent:
                    continue
                
                if find_path(neighbor, node, target, path):
                    return True
            
            path.pop()
            return False
        
        for start, end in trips:
            path = []
            find_path(start, -1, end, path)
            
            for node in path:
                frequency[node] += 1
        
        def dfs(node: int, parent: int):
            not_halved = frequency[node] * price[node]
            halved = frequency[node] * (price[node] // 2)
            
            for neighbor in graph[node]:
                if neighbor == parent:
                    continue
                
                child_not_halved, child_halved = dfs(neighbor, node)
                
                not_halved += min(child_not_halved, child_halved)
                
                halved += child_not_halved
            
            return not_halved, halved
        
        return min(dfs(0, -1))

The implementation begins by constructing the adjacency list representation of the tree.

Next, the algorithm computes node frequencies. For each trip, DFS finds the unique path between the start and end nodes. Every node on that path has its frequency incremented.

Once frequencies are known, the algorithm performs tree DP using another DFS traversal.

For every node:

  • not_halved stores the minimum subtree cost when this node keeps its original price.
  • halved stores the minimum subtree cost when this node's price is halved.

When a node is halved, its children cannot be halved because adjacent discounted nodes are forbidden.

Finally, the root returns the minimum of the two possible states.

Go Solution

package main

func minimumTotalPrice(n int, edges [][]int, price []int, trips [][]int) int {
	graph := make([][]int, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]

		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	frequency := make([]int, n)

	var findPath func(int, int, int, *[]int) bool

	findPath = func(node int, parent int, target int, path *[]int) bool {
		*path = append(*path, node)

		if node == target {
			return true
		}

		for _, neighbor := range graph[node] {
			if neighbor == parent {
				continue
			}

			if findPath(neighbor, node, target, path) {
				return true
			}
		}

		*path = (*path)[:len(*path)-1]
		return false
	}

	for _, trip := range trips {
		start := trip[0]
		end := trip[1]

		path := []int{}

		findPath(start, -1, end, &path)

		for _, node := range path {
			frequency[node]++
		}
	}

	var dfs func(int, int) (int, int)

	dfs = func(node int, parent int) (int, int) {
		notHalved := frequency[node] * price[node]
		halved := frequency[node] * (price[node] / 2)

		for _, neighbor := range graph[node] {
			if neighbor == parent {
				continue
			}

			childNotHalved, childHalved := dfs(neighbor, node)

			if childNotHalved < childHalved {
				notHalved += childNotHalved
			} else {
				notHalved += childHalved
			}

			halved += childNotHalved
		}

		return notHalved, halved
	}

	a, b := dfs(0, -1)

	if a < b {
		return a
	}

	return b
}

The Go implementation closely mirrors the Python version.

The main difference is explicit slice management during DFS path construction. Since slices are passed by value, the path slice is passed by pointer so recursive modifications are preserved correctly.

Go also lacks tuple syntax, so multiple return values are used for DP states.

Integer overflow is not a concern because the maximum possible answer is small relative to Go's integer range.

Worked Examples

Example 1

n = 4
edges = [[0,1],[1,2],[1,3]]
price = [2,2,10,6]
trips = [[0,3],[2,1],[2,3]]

Step 1: Build frequency table

Tree:

0 - 1 - 2
    |
    3

Process trips one by one.

Trip Path Frequency Updates
[0,3] 0 → 1 → 3 freq = [1,1,0,1]
[2,1] 2 → 1 freq = [1,2,1,1]
[2,3] 2 → 1 → 3 freq = [1,3,2,2]

Final frequencies:

freq = [1,3,2,2]

Step 2: Compute contributions

Node Price Frequency Normal Cost Halved Cost
0 2 1 2 1
1 2 3 6 3
2 10 2 20 10
3 6 2 12 6

Step 3: Tree DP

Start from leaves.

Node 2

State Cost
Not halved 20
Halved 10

Node 3

State Cost
Not halved 12
Halved 6

Node 1

If not halved:

6 + min(20,10) + min(12,6)
= 6 + 10 + 6
= 22

If halved:

3 + 20 + 12
= 35

Node 0

If not halved:

2 + min(22,35)
= 24

If halved:

1 + 22
= 23

Answer:

23

Example 2

n = 2
edges = [[0,1]]
price = [2,2]
trips = [[0,0]]

Step 1: Frequency counting

Path:

0

Frequency:

freq = [1,0]

Step 2: DP values

Node Normal Halved
0 2 1
1 0 0

Root result:

min(2,1) = 1

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(trips × n + n) DFS path search for each trip plus tree DP
Space O(n) Adjacency list, recursion stack, frequency array

The path-finding DFS may visit all nodes for each trip, giving O(trips × n) complexity. Since n <= 50, this is very efficient.

The DP traversal processes each edge exactly once, contributing linear complexity.

Test Cases

from typing import List

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        frequency = [0] * n

        def find_path(node, parent, target, path):
            path.append(node)

            if node == target:
                return True

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                if find_path(neighbor, node, target, path):
                    return True

            path.pop()
            return False

        for start, end in trips:
            path = []
            find_path(start, -1, end, path)

            for node in path:
                frequency[node] += 1

        def dfs(node, parent):
            not_halved = frequency[node] * price[node]
            halved = frequency[node] * (price[node] // 2)

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                child_not, child_half = dfs(neighbor, node)

                not_halved += min(child_not, child_half)
                halved += child_not

            return not_halved, halved

        return min(dfs(0, -1))

solution = Solution()

# Example 1 from problem statement
assert solution.minimumTotalPrice(
    4,
    [[0,1],[1,2],[1,3]],
    [2,2,10,6],
    [[0,3],[2,1],[2,3]]
) == 23

# Example 2 from problem statement
assert solution.minimumTotalPrice(
    2,
    [[0,1]],
    [2,2],
    [[0,0]]
) == 1

# Single node tree
assert solution.minimumTotalPrice(
    1,
    [],
    [8],
    [[0,0]]
) == 4

# Chain tree
assert solution.minimumTotalPrice(
    3,
    [[0,1],[1,2]],
    [2,4,6],
    [[0,2]]
) == 8

# Star topology
assert solution.minimumTotalPrice(
    5,
    [[0,1],[0,2],[0,3],[0,4]],
    [10,2,2,2,2],
    [[1,2],[3,4]]
) == 18

# Multiple repeated trips
assert solution.minimumTotalPrice(
    3,
    [[0,1],[1,2]],
    [2,10,2],
    [[0,2],[0,2],[0,2]]
) == 21

# No benefit from halving center node
assert solution.minimumTotalPrice(
    3,
    [[0,1],[1,2]],
    [100,2,100],
    [[0,2]]
) == 102

# Balanced tree
assert solution.minimumTotalPrice(
    7,
    [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]],
    [4,6,8,2,2,2,2],
    [[3,4],[5,6],[3,6]]
) > 0
Test Why
Example 1 Validates general tree DP behavior
Example 2 Validates single-node path handling
Single node tree Tests smallest possible tree
Chain tree Tests linear topology
Star topology Tests adjacency restriction around center
Multiple repeated trips Ensures frequency accumulation works
Expensive endpoints Ensures optimal node selection
Balanced tree Tests larger recursive structure

Edge Cases

One important edge case is a trip where the start and end nodes are the same. In this situation, the path contains exactly one node. A buggy implementation might incorrectly assume paths always contain edges. The DFS path construction in this solution correctly handles this because it immediately returns when the current node equals the target.

Another important case is a chain-shaped tree. In a linear structure, every node except the ends has two neighbors, making adjacency constraints more restrictive. Greedy strategies often fail here because halving one node prevents halving adjacent high-value nodes. The tree DP handles this naturally through its parent-child state transitions.

A third critical edge case is when one node appears in many trips. Such nodes contribute disproportionately to the total cost, making them attractive candidates for halving. However, if neighboring nodes also have large contributions, choosing the locally largest savings may not produce the global optimum. The DP explores both possibilities for every subtree, ensuring the globally minimal configuration is found.