2646. Minimize the Total Price of the Trips LeetCode Solution
In this guide, you will get 2646. Minimize the Total Price of the Trips LeetCode Solution with the best time and space complexity. The solution to Minimize the Total Price of the Trips problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimize the Total Price of the Trips
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.
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
Complexity Analysis
Time Complexity: O(n \cdot |\texttt{trips}|)
Space Complexity: O(n)
2646. Minimize the Total Price of the Trips LeetCode Solution in C++
class Solution {
public:
int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price,
vector<vector<int>>& trips) {
vector<vector<int>> graph(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
// count[i] := the number of times node i is traversed
vector<int> count(n);
for (const vector<int>& trip : trips) {
const int start = trip[0];
const int end = trip[1];
vector<int> path;
dfsCount(graph, start, /*prev=*/-1, end, count, path);
}
vector<vector<int>> mem(n, vector<int>(2, -1));
return dfs(graph, 0, -1, price, count, false, mem);
}
private:
void dfsCount(const vector<vector<int>>& graph, int u, int prev, int end,
vector<int>& count, vector<int>& path) {
path.push_back(u);
if (u == end) {
for (const int i : path)
++count[i];
return;
}
for (const int v : graph[u])
if (v != prev)
dfsCount(graph, v, u, end, count, path);
path.pop_back();
}
// Returns the minimum price sum for the i-th node, where its parent is
// halved parent or not halved not.
int dfs(const vector<vector<int>>& graph, int u, int prev,
const vector<int>& price, const vector<int>& count, int parentHalved,
vector<vector<int>>& mem) {
if (mem[u][parentHalved] != -1)
return mem[u][parentHalved];
int sumWithFullNode = price[u] * count[u];
for (const int v : graph[u])
if (v != prev)
sumWithFullNode += dfs(graph, v, u, price, count, false, mem);
if (parentHalved) // Can't halve this node if its parent was halved.
return mem[u][parentHalved] = sumWithFullNode;
int sumWithHalvedNode = (price[u] / 2) * count[u];
for (const int v : graph[u])
if (v != prev)
sumWithHalvedNode += dfs(graph, v, u, price, count, true, mem);
return mem[u][parentHalved] = min(sumWithFullNode, sumWithHalvedNode);
}
}; /* code provided by PROGIEZ */
2646. Minimize the Total Price of the Trips LeetCode Solution in Java
class Solution {
public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; i++)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[u].add(v);
graph[v].add(u);
}
// count[i] := the number of times node i is traversed
int[] count = new int[n];
for (int[] trip : trips) {
final int start = trip[0];
final int end = trip[1];
dfsCount(graph, start, -1, end, count, /*path=*/new ArrayList<>());
}
Integer[][] mem = new Integer[n][2];
return dfs(graph, 0, -1, price, count, false, mem);
}
private void dfsCount(List<Integer>[] graph, int u, int prev, int end, int[] count,
List<Integer> path) {
path.add(u);
if (u == end) {
for (final int i : path)
++count[i];
return;
}
for (final int v : graph[u])
if (v != prev)
dfsCount(graph, v, u, end, count, path);
path.remove(path.size() - 1);
}
// Returns the minimum price sum for the i-th node, where its parent is
// halved parent or not halved not.
private int dfs(List<Integer>[] graph, int u, int prev, int[] price, int[] count,
boolean parentHalved, Integer[][] mem) {
if (mem[u][parentHalved ? 1 : 0] != null)
return mem[u][parentHalved ? 1 : 0];
int sumWithFullNode = price[u] * count[u];
for (final int v : graph[u])
if (v != prev)
sumWithFullNode += dfs(graph, v, u, price, count, false, mem);
if (parentHalved) // Can't halve this node if its parent was halved.
return mem[u][1] = sumWithFullNode;
int sumWithHalvedNode = (price[u] / 2) * count[u];
for (int v : graph[u])
if (v != prev)
sumWithHalvedNode += dfs(graph, v, u, price, count, true, mem);
return mem[u][parentHalved ? 1 : 0] = Math.min(sumWithFullNode, sumWithHalvedNode);
}
} // code provided by PROGIEZ
2646. Minimize the Total Price of the Trips LeetCode Solution in Python
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)
# count[i] := the number of times i is traversed
count = [0] * n
def dfsCount(u: int, prev: int, end: int, path: list[int]) -> None:
path.append(u)
if u == end:
for i in path:
count[i] += 1
return
for v in graph[u]:
if v != prev:
dfsCount(v, u, end, path)
path.pop()
for start, end in trips:
dfsCount(start, -1, end, [])
@functools.lru_cache(None)
def dfs(u: int, prev: int, parentHalved: bool) -> int:
"""
Returns the minimum price sum for the i-th node, where its parent is
halved parent or not halved not.
"""
sumWithFullNode = price[u] * count[u] + sum(dfs(v, u, False)
for v in graph[u]
if v != prev)
if parentHalved: # Can't halve this node if its parent was halved.
return sumWithFullNode
sumWithHalvedNode = (price[u] // 2) * count[u] + sum(dfs(v, u, True)
for v in graph[u]
if v != prev)
return min(sumWithFullNode, sumWithHalvedNode)
return dfs(0, -1, False) # code by PROGIEZ
