#2646

Hard

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Minimize the Total Price of the Trips

Calculate the minimum total cost of multiple trips on a tree by selectively halving node prices using DFS frequency counts.

array dynamic programming tree depth first search graph

Problem Statement

You are given a tree with n nodes labeled from 0 to n - 1. Each node i has a price price[i]. You are also given a list of trips, each defined by a start and end node. Each trip incurs a cost equal to the sum of prices of all nodes on the path from start to end.

You may choose any subset of nodes and halve their prices to minimize the total cost across all trips. Determine the minimum possible total cost. The tree is represented as an edge list, and every node price is even.

Examples

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

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

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

Solution Approach

Compute Node Visit Frequencies via DFS

Traverse each trip path using depth-first search to record how many times each node is visited. Store these frequencies in an array freq[i] representing node i visits, since the total price contribution depends on how often nodes are traversed.

Dynamic Programming on Tree for Price Minimization

Use a post-order DFS to calculate two DP states for each node: the minimum cost if its price is halved, and if it is not. Combine children's DP states to propagate optimal choices upward, ensuring the final total minimizes the sum over all trips.

Compute Final Minimum Total Cost

Multiply each node's price by its frequency from all trips, applying halving according to DP decisions. Sum these adjusted contributions to obtain the minimum total cost across all trips, effectively leveraging both DFS frequency counting and tree DP.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * trips) for computing DFS paths plus O(n) for the DP traversal. Space complexity is O(n) for frequency array and DP states, keeping memory usage linear relative to the number of nodes.

What Interviewers Usually Probe

Check if the candidate identifies DFS as the tool for counting node frequencies.
Listen for correct formulation of two DP states per node to consider halving or not.
Observe if they optimize repeated trip paths using memoization or frequency accumulation.

Common Pitfalls or Variants

Common pitfalls

Forgetting to count multiple visits of a node across different trips, underestimating its contribution.
Incorrectly combining DP states, leading to non-optimal halving choices.
Attempting brute-force path enumeration without DFS, resulting in timeouts even for small n.

Follow-up variants

Instead of halving node prices, consider reducing each node price by a fixed amount and compute minimum total cost.
Allow edges to have weights and optimize trips cost including edge weights along with node prices.
Limit the number of nodes that can be halved and find the minimal achievable total trip cost.

FAQ

What is the main algorithmic pattern for Minimize the Total Price of the Trips?

The core pattern is graph traversal with depth-first search combined with dynamic programming on trees to minimize repeated node contributions.

How do I calculate the frequency of node visits across all trips?

Use DFS for each trip to trace the path from start to end, incrementing a frequency counter for every node encountered.

Can nodes be halved more than once?

No, each node price can only be halved once. The DP ensures the best subset of nodes is selected to minimize the total cost.

What are common mistakes when solving this problem?

Common mistakes include ignoring multiple visits of nodes across trips, miscalculating DP states, and using brute-force path enumeration.

Is this problem solvable without dynamic programming?

Not efficiently; without DP, choosing which nodes to halve may require exponential checks over subsets, making it infeasible even for n = 50.

terminal

Solution

Solution 1: Enumeration

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Solution:
    def minimumTotalPrice(
        self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]
    ) -> int:
        def dfs(i: int, fa: int, k: int) -> bool:
            cnt[i] += 1
            if i == k:
                return True
            ok = any(j != fa and dfs(j, i, k) for j in g[i])
            if not ok:
                cnt[i] -= 1
            return ok

        def dfs2(i: int, fa: int) -> (int, int):
            a = cnt[i] * price[i]
            b = a // 2
            for j in g[i]:
                if j != fa:
                    x, y = dfs2(j, i)
                    a += min(x, y)
                    b += x
            return a, b

        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        cnt = Counter()
        for start, end in trips:
            dfs(start, -1, end)
        return min(dfs2(0, -1))

Continue Practicing

#2581 count number of possible root nodes #2467 most profitable path in a tree #2368 reachable nodes with restrictions