2646. Minimize the Total Price of the Trips

HardTreeDepth-First SearchGraphArrayDynamic Programming
Leetcode Link

Problem Description

In this problem, we are tasked with finding the minimum total price sum of trips across an undirected tree. The tree consists of n nodes, each with an associated price. Connections between the nodes are described by the edges list, where each edge is a connection between two nodes.

For the trips, we have a list of pairs indicating starting and ending nodes for each trip. A unique aspect of this problem is the ability to halve the prices of some non-adjacent nodes before starting any trips. This presents an optimization problem where we need to decide which node prices to reduce in order to minimize the total cost of all trips.

The goal is to determine the minimum possible sum of prices for all trips.

Intuition

The intuition behind the solution lies in understanding that we have two key tasks:

  1. Track the paths taken during the trips to see how many times each node is visited.
  2. Decide which nodes' prices should be halved to minimize the overall cost, taking into account their frequency of being on a trip path and ensuring the chosen nodes are not adjacent.

To solve the first task, we use a Depth-First Search (DFS) approach. We perform DFS for each trip to mark the frequency at which each node is visited on any path from the start to the end of that trip.

For the second task, we again apply a DFS approach. This time, we calculate for each node the total price of the sub-tree rooted at that node with and without halving its price. To ensure that prices are halved only for non-adjacent nodes, we compare the total cost with halved price at each node with the sum of minimum costs from its children.

Overall, by using DFS, we can ensure we visit each node and process them while adhering to the given constraints of the problem.

Learn more about Tree, Depth-First Search, Graph and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Solution Approach

The solution uses depth-first search (DFS), a graph traversal algorithm, to explore the tree and solve the two main tasks: tracking paths and minimizing the total price sum.

Here are the steps that comprise the solution approach:

  1. Building the Graph: The graph is represented using an adjacency list, which is a common efficient way to store a graph when dealing with sparse trees. Each node is indexed from 0 to n - 1, and the adjacency list g maintains a list of children for every node.

  2. Counting Visits (DFS): A DFS is performed through the function dfs(i: int, fa: int, k: int). This function is called for each trip to track how many times the nodes are visited across all trips. The function uses two parameters, i for the current node and fa for the parent node, to avoid revisiting the parent node during the recursion. The count for each node is increased when it is visited, and if we reach the end node of the trip (k), we return True. If the current path does not lead to k, we undo the increment on cnt[i] before backtracking. This process is performed for all trips and effectively maps the usage frequency of each node across all trips.

  3. Halving Prices and Cost Calculation (DFS): Another DFS function, dfs2(i: int, fa: int), is called to find the sum of prices for the sub-tree rooted at each node i, considering the option to halve the node's price. The function calculates two costs: a, which is the cost without any price halving, and b, which is with the node's price halved. For each child j, we recursively call dfs2(j, i) to obtain the optimal costs for the child's sub-tree and accumulate these costs. The crucial part is to choose the minimum between x and y for the cost a to reflect the best decision for non-adjacent nodes' price reduction, while b always includes the lower child costs as we're halving i's price.

  4. Final Minimum Cost: The final step is to call dfs2(0, -1) for the root of the tree (noting that -1 indicates there is no parent for the root) to get the minimum overall price with and without halving the price of the root node. The minimum of these two values is the answer to the problem as we track the minimum cost for the whole tree.

The use of Python's Counter from the collections module helps in handling the node visit counts with convenience, avoiding manual initialization and incrementing of counts for every node. The recursive nature of DFS elegantly handles the complex conditions of the problem by breaking it down into smaller sub-problems of the tree.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the maximum element can be found in:

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have a tree with 5 nodes where the prices are as follows: [2, 1, 3, 2, 2] and the edges list that defines the connections is [[0, 1], [0, 2], [2, 3], [2, 4]]. We have 2 trips: one from node 1 to 3 and another from node 1 to 4.

The adjacency list g for our tree would look like this:

1{
20: [1, 2],
31: [0],
42: [0, 3, 4],
53: [2],
64: [2]
7}

  1. Building the Graph: We create the adjacency list g to represent our tree based on the edges.

  2. Counting Visits (DFS): We perform DFS to count visits for each trip:

    • For trip 1 to 3, DFS traversal is as follows: 1 -> 0 -> 2 -> 3. We increment the visit count for these nodes.
    • For trip 1 to 4, DFS traversal is: 1 -> 0 -> 2 -> 4. We increment the visit count for these nodes.

After counting visits, our visit counts (ignoring nodes with 0 visits) might look like: {1: 2, 0: 2, 2: 2, 3: 1, 4: 1}.

  1. Halving Prices and Cost Calculation (DFS): We perform another DFS to calculate the optimal cost for each node's sub-tree:
    • Starting with dfs2(0, -1), we consider halving the price of node 0. We find the cost of sub-trees 1, 3, and 4 through recursive calls.
    • For node 2, we recursively find the best cost of sub-trees 3 and 4, and so on for each node.

By the end of this step, we have determined the minimum cost for each node's sub-tree, considering the option of halving the node's price.

  1. Final Minimum Cost: The result of dfs2(0, -1) would give us two values: the minimum cost of trips without halving the price of the root, and the minimum cost of trips with the root price halved. The minimum of these two values will give us the final answer to the problem.

By following these steps and applying DFS effectively, we track each nodeโ€™s frequency of visit and decide strategically which non-adjacent nodes should have their prices halved to minimize the total cost of all trips. In this example, the result might indicate halving the price of either the most frequently visited non-adjacent node or the node that gives the maximum saving when its price is halved, depending on the specific visit counts and node prices.

Solution Implementation

1from typing import List
2from collections import Counter
3
4class Solution:
5    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
6        # A DFS helper function to count the number of trips passing through each node.
7        def dfs(current_node: int, parent_node: int, destination: int) -> bool:
8            trip_count[current_node] += 1
9            if current_node == destination:
10                return True
11          
12            path_exists = any(
13                neighbor != parent_node and dfs(neighbor, current_node, destination)
14                for neighbor in graph[current_node]
15            )
16          
17            if not path_exists:
18                trip_count[current_node] -= 1
19              
20            return path_exists
21
22        # A DFS helper function to compute the minimum total price to visit all nodes,
23        # considering the count of trips passing through each node.
24        def dfs_min_price(current_node: int, parent_node: int) -> (int, int):
25            full_price = trip_count[current_node] * price[current_node]
26            half_price = full_price // 2
27
28            for neighbor in graph[current_node]:
29                if neighbor != parent_node:
30                    min_full, min_half = dfs_min_price(neighbor, current_node)
31                    full_price += min(min_full, min_half)
32                    half_price += min_full
33
34            return full_price, half_price
35
36        # Construct the graph from edges.
37        graph = [[] for _ in range(n)]
38        for a, b in edges:
39            graph[a].append(b)
40            graph[b].append(a)
41          
42        # Count the number of trips that pass through each node.
43        trip_count = Counter()
44        for start, end in trips:
45            dfs(start, -1, end)
46          
47        # Calculate the minimum total price considering both full price and half price tickets.
48        full_price, half_price = dfs_min_price(0, -1)
49        return min(full_price, half_price)
50
51
52# Note: The comments have been added to explain the functions and logic used in the code.
53# All variable and method names are kept consistent with Python 3 standards.
54
1class Solution {
2    private List<Integer>[] graph;
3    private int[] price;
4    private int[] count;
5
6    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
7        this.price = price;
8        count = new int[n];
9        graph = new List[n];
10        Arrays.setAll(graph, k -> new ArrayList<>());
11        // Construct the undirected graph
12        for (int[] edge : edges) {
13            int from = edge[0], to = edge[1];
14            graph[from].add(to);
15            graph[to].add(from);
16        }
17        // Count the frequencies of nodes being on the path from start to end for each trip
18        for (int[] trip : trips) {
19            int start = trip[0], end = trip[1];
20            depthFirstSearch(start, -1, end);
21        }
22        // Calculate the minimum price
23        int[] answer = secondDepthFirstSearch(0, -1);
24        return Math.min(answer[0], answer[1]);
25    }
26
27    // Helper DFS method to count the frequency of each node on the path from 'start' to 'k'
28    private boolean depthFirstSearch(int current, int parent, int destination) {
29        ++count[current];
30        if (current == destination) {
31            return true;
32        }
33        boolean found = false;
34        for (int neighbor : graph[current]) {
35            if (neighbor != parent) {
36                found = depthFirstSearch(neighbor, current, destination);
37                if (found) {
38                    break;
39                }
40            }
41        }
42        if (!found) {
43            --count[current];
44        }
45        return found;
46    }
47
48    // Helper DFS method to compute two prices from each node to child nodes:
49    // 1. The price of traveling through node 'i' based on the frequency.
50    // 2. The price of travel avoiding node 'i' if possible.
51    private int[] secondDepthFirstSearch(int current, int parent) {
52        int directTotalPrice = count[current] * price[current]; // price if using this node
53        int bypassedTotalPrice = directTotalPrice >> 1; // half price if bypassing this node
54        for (int neighbor : graph[current]) {
55            if (neighbor != parent) {
56                int[] prices = secondDepthFirstSearch(neighbor, current);
57                directTotalPrice += Math.min(prices[0], prices[1]); // min price from this node to its children
58                bypassedTotalPrice += prices[0]; // full price if this node is bypassed
59            }
60        }
61        return new int[] {directTotalPrice, bypassedTotalPrice};
62    }
63}
64
1#include<vector>
2#include<functional>
3using namespace std;
4
5class Solution {
6public:
7    // Function to find the minimum total price to pay for the trips.
8    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
9        // Adjacency list to represent the graph.
10        vector<vector<int>> graph(n);
11        // Count of how many times a node is visited during the trips.
12        vector<int> visitCount(n);
13      
14        // Build the undirected graph from the edges.
15        for (auto& edge : edges) {
16            int a = edge[0], b = edge[1];
17            graph[a].push_back(b);
18            graph[b].push_back(a);
19        }
20      
21        // Depth-first search to increment the visit count on the path from start to end.
22        // i: current node, parent: parent node, destination: destination node.
23        function<bool(int, int, int)> dfs = [&](int currentNode, int parentNode, int destination) -> bool {
24            visitCount[currentNode]++;
25            if (currentNode == destination) {
26                return true;
27            }
28            bool pathExists = false;
29            for (int neighbor : graph[currentNode]) {
30                if (neighbor != parentNode) {
31                    pathExists = dfs(neighbor, currentNode, destination);
32                    if (pathExists) {
33                        break; // If the destination is found, break out of the loop.
34                    }
35                }
36            }
37            if (!pathExists) {
38                visitCount[currentNode]--; // If no path, decrement the visit count.
39            }
40            return pathExists;
41        };
42      
43        // Second depth-first search to compute the total price to pay.
44        // i: current node, parent: parent node.
45        function<pair<int, int>(int, int)> dfs2 = [&](int currentNode, int parentNode) -> pair<int, int> {
46            int fullPrice = visitCount[currentNode] * price[currentNode];
47            int halfPrice = fullPrice >> 1; // Bitwise shift to divide by 2.
48            for (int neighbor : graph[currentNode]) {
49                if (neighbor != parentNode) {
50                    auto [fullNeighborPrice, halfNeighborPrice] = dfs2(neighbor, currentNode);
51                    fullPrice += min(fullNeighborPrice, halfNeighborPrice);
52                    halfPrice += fullNeighborPrice;
53                }
54            }
55            return {fullPrice, halfPrice};
56        };
57      
58        // Run the first depth-first search for each trip to update the visit count.
59        for (auto& trip : trips) {
60            int start = trip[0], end = trip[1];
61            dfs(start, -1, end);
62        }
63      
64        // Call the second depth-first search from the root node to calculate the total price.
65        auto [fullPriceResult, halfPriceResult] = dfs2(0, -1);
66      
67        // Return the minimum of the two calculated prices.
68        return min(fullPriceResult, halfPriceResult);
69    }
70};
71
1// Function to calculate the minimum total price for all trips.
2// n: number of locations, edges: list of connections between locations,
3// price: array where each index represents a price for the location,
4// trips: list of trips represented by [start, end],
5// returns the minimum total price for all trips.
6function minimumTotalPrice(
7  n: number,
8  edges: number[][],
9  price: number[],
10  trips: number[][],
11): number {
12  // Create a graph as an adjacency list.
13  const graph: number[][] = Array.from({ length: n }, () => []);
14  for (const [from, to] of edges) {
15    graph[from].push(to);
16    graph[to].push(from);
17  }
18
19  // Initialize an array to count the number of trips through each location.
20  const tripCount: number[] = new Array(n).fill(0);
21
22  // Depth-first search function to count trip occurrences between start and end.
23  // i: current location, parent: parent location, destination: trip's destination:
24  // returns boolean indicating if the destination was reached in the search.
25  const depthFirstSearch = (i: number, parent: number, destination: number): boolean => {
26    tripCount[i]++;
27    if (i === destination) {
28      return true;
29    }
30    let reachedDestination = false;
31    for (const next of graph[i]) {
32      if (next !== parent) {
33        reachedDestination = depthFirstSearch(next, i, destination);
34        if (reachedDestination) {
35          break;
36        }
37      }
38    }
39    if (!reachedDestination) {
40      tripCount[i]--;
41    }
42    return reachedDestination;
43  };
44
45  // Count trip occurrences for each trip in the trips array.
46  for (const [start, end] of trips) {
47    depthFirstSearch(start, -1, end);
48  }
49
50  // Second depth-first search function to calculate the total cost with discounts.
51  // i: current location, parent: parent location:
52  // returns array with total cost without discount, and with discount.
53  const calculateCosts = (i: number, parent: number): number[] => {
54    let totalCostWithoutDiscount: number = price[i] * tripCount[i];
55    let totalCostWithDiscount: number = totalCostWithoutDiscount >> 1;
56    for (const next of graph[i]) {
57      if (next !== parent) {
58        const [costWithoutDiscount, costWithDiscount] = calculateCosts(next, i);
59        totalCostWithoutDiscount += Math.min(costWithoutDiscount, costWithDiscount);
60        totalCostWithDiscount += costWithoutDiscount;
61      }
62    }
63    return [totalCostWithoutDiscount, totalCostWithDiscount];
64  };
65
66  // Calculate the costs from the starting location.
67  const [costWithoutDiscount, costWithDiscount] = calculateCosts(0, -1);
68
69  // Return the minimum of the two calculated costs.
70  return Math.min(costWithoutDiscount, costWithDiscount);
71}
72
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Time and Space Complexity

Time Complexity

The time complexity of the code consists of two parts: building the graph and performing depth-first search (DFS) operations.

  • Building the graph from the input edges requires iterating through each edge once. Since there are E edges provided where E is the length of the edges list, this part has a complexity of O(E).

  • The dfs function is called for each trip to find the path from the start to the end. The path for a given trip is found by traversing the graph using DFS. In the worst case, this can go up to O(n) for each trip because we need to visit all the nodes. Since there are T trips provided where T is the length of the trips list, this part has a complexity of O(T * n).

  • The dfs2 function is called once and it potentially visits each node once and computes the minimum price for each node. This part has a complexity of O(n) since it runs a DFS on the graph with n nodes.

Combining these, the total time complexity is O(E + T * n + n). Since E is typically less than n^2 and T could be up to n, the combined complexity could be viewed as O(n^2) in the worst case when considering dense graphs and a high number of trips.

Space Complexity

The space complexity is dominated by the space needed to store the graph, the cnt counter, and the recursive stack for the DFS operations.

  • The graph is represented as an adjacency list, which in the worst case stores an entry for each edge twice (since the graph is undirected). Therefore, the space complexity for the graph is O(E).

  • The cnt Counter object keeps a count of nodes for the number of trips that pass through them. In the worst case, all trips will involve all nodes, thus the Counter would have n entries. This would take O(n) space.

  • The recursive stack for the dfs and dfs2 functions would at worst case store a context for each node in a chain-like sequence of nodes (O(n) space).

The combined space complexity hence is O(E + n + n) which simplifies to O(E + n). Since E can at most be n(n-1)/2 for a complete graph, the space complexity can be O(n^2) in the worst case.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ