Minimize the Total Price of the Trips — Problem & Solution
Minimize the Total Price of the Trips solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimize the Total Price of the Trips is a hard coding problem on arrays, dynamic programming and depth-first search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Depth-First Search, Trees, Graph
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected tree has n nodes numbered 0 to n - 1, joined by the n - 1 edges in edges. Every node has an even price price[i].
The price of a path is the sum of the prices of every node on it (both ends included). You will make the trips trips[i] = [start, end], each along the unique path from start to end.
Before the first trip you may pick a set of pairwise non-adjacent nodes and halve their prices. Return the minimum total price of all the 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: Halve nodes 0, 2 and 3 (no two are adjacent): the prices become [1,2,5,3]. The trips cost 1+2+3 = 6, 5+2 = 7 and 5+2+3 = 10, a total of 23.
Example 2
Input: n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
Output: 1
Explanation: Halve node 0; the single trip stays on node 0 and costs 1.
Example 3
Input: n = 1, edges = [], price = [6], trips = [[0,0],[0,0]]
Output: 6
Constraints
1 <= n <= 50edges.length == n - 10 <= a, b <= n - 1edges represents a valid treeprice.length == nprice[i] is even1 <= price[i] <= 10001 <= trips.length <= 1000 <= start, end <= n - 1
Hints for Minimize the Total Price of the Trips
Hint 1
The trips do not depend on the halving, so first count, for every node, how many trips pass through it. Then a node costs
count · pricein full orcount · price / 2when halved.Hint 2
With n ≤ 50 and at most 100 trips, walking each trip's path explicitly (find the path with a DFS from its start) is cheap.
Hint 3
Choosing non-adjacent nodes to minimise a weighted sum on a tree is the 'house robber on a tree' DP: for each node keep the best subtree cost with the node halved and with it not halved.
How to solve Minimize the Total Price of the Trips
Split the problem in two. The trips fix how many times each node is paid for, cnt[v]. What remains is choosing an independent set of nodes to halve so that Σ cnt[v]·price[v]·(1 or 1/2) is smallest — a classic two-state tree DP.
Approach
- For each trip, find parents by a DFS/BFS from
startand walk back fromend, adding 1 tocntof every node on the path. - Root the tree at 0. Process nodes children-first and keep
full[v](v keeps its price) andhalf[v](v is halved). full[v] = cnt[v]·price[v] + Σ min(full[c], half[c])andhalf[v] = cnt[v]·price[v]/2 + Σ full[c]over the childrenc.- Return
min(full[0], half[0]).
Why it works
The total price is a sum over nodes of cnt[v] times the node's (possibly halved) price, so the trip structure only enters through cnt. On a tree, whether v is halved only constrains its children (they must not be), so the two states per node capture every valid choice and the DP is exact.
Complexity
- Time —
O(n · trips) - Space —
O(n)
Pitfalls
- A trip may start and end at the same node; its path is that single node.
- Prices are even, so halving stays an integer.
- Halving is decided once for all trips — do not optimise each trip separately.
Reference solution
Python
from typing import List
def minimumTotalPrice(n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
cnt = [0] * n
for s, t in trips:
par = [-2] * n
par[s] = -1
stack = [s]
while stack:
u = stack.pop()
for v in adj[u]:
if par[v] == -2:
par[v] = u
stack.append(v)
x = t
while x != -1:
cnt[x] += 1
x = par[x]
parent = [-1] * n
order = []
seen = [False] * n
seen[0] = True
stack = [0]
while stack:
u = stack.pop()
order.append(u)
for v in adj[u]:
if not seen[v]:
seen[v] = True
parent[v] = u
stack.append(v)
full = [cnt[v] * price[v] for v in range(n)]
half = [cnt[v] * price[v] // 2 for v in range(n)]
for u in reversed(order):
p = parent[u]
if p >= 0:
full[p] += min(full[u], half[u])
half[p] += full[u]
return min(full[0], half[0])Java
public static int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
int[] cnt = new int[n];
int[] par = new int[n], stack = new int[n];
for (int[] trip : trips) {
Arrays.fill(par, -2);
par[trip[0]] = -1;
int sp = 0;
stack[sp++] = trip[0];
while (sp > 0) {
int u = stack[--sp];
for (int v : adj.get(u)) if (par[v] == -2) { par[v] = u; stack[sp++] = v; }
}
for (int x = trip[1]; x != -1; x = par[x]) cnt[x]++;
}
int[] parent = new int[n], order = new int[n];
boolean[] seen = new boolean[n];
Arrays.fill(parent, -1);
int sp = 0, k = 0;
stack[sp++] = 0;
seen[0] = true;
while (sp > 0) {
int u = stack[--sp];
order[k++] = u;
for (int v : adj.get(u)) if (!seen[v]) { seen[v] = true; parent[v] = u; stack[sp++] = v; }
}
int[] full = new int[n], half = new int[n];
for (int v = 0; v < n; v++) { full[v] = cnt[v] * price[v]; half[v] = cnt[v] * price[v] / 2; }
for (int p = n - 1; p >= 0; p--) {
int z = order[p], pz = parent[z];
if (pz >= 0) { full[pz] += Math.min(full[z], half[z]); half[pz] += full[z]; }
}
return Math.min(full[0], half[0]);
}C++
int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
vector<vector<int>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
vector<int> cnt(n, 0), par(n);
for (auto& trip : trips) {
fill(par.begin(), par.end(), -2);
par[trip[0]] = -1;
vector<int> st = {trip[0]};
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int v : adj[u]) if (par[v] == -2) { par[v] = u; st.push_back(v); }
}
for (int x = trip[1]; x != -1; x = par[x]) cnt[x]++;
}
vector<int> parent(n, -1), order, st = {0};
vector<bool> seen(n, false);
seen[0] = true;
while (!st.empty()) {
int u = st.back();
st.pop_back();
order.push_back(u);
for (int v : adj[u]) if (!seen[v]) { seen[v] = true; parent[v] = u; st.push_back(v); }
}
vector<int> full(n), half(n);
for (int v = 0; v < n; v++) { full[v] = cnt[v] * price[v]; half[v] = cnt[v] * price[v] / 2; }
for (int p = n - 1; p >= 0; p--) {
int z = order[p], pz = parent[z];
if (pz >= 0) { full[pz] += min(full[z], half[z]); half[pz] += full[z]; }
}
return min(full[0], half[0]);
}JavaScript
var minimumTotalPrice = function(n, edges, price, trips) {
var adj = [];
for (var i = 0; i < n; i++) adj.push([]);
for (var e = 0; e < edges.length; e++) { adj[edges[e][0]].push(edges[e][1]); adj[edges[e][1]].push(edges[e][0]); }
var cnt = new Array(n);
for (var c = 0; c < n; c++) cnt[c] = 0;
for (var t = 0; t < trips.length; t++) {
var par = new Array(n);
for (var k = 0; k < n; k++) par[k] = -2;
par[trips[t][0]] = -1;
var st = [trips[t][0]];
while (st.length > 0) {
var u = st.pop();
for (var j = 0; j < adj[u].length; j++) { var v = adj[u][j]; if (par[v] === -2) { par[v] = u; st.push(v); } }
}
for (var x = trips[t][1]; x !== -1; x = par[x]) cnt[x]++;
}
var parent = new Array(n), seen = new Array(n), order = [];
for (var a = 0; a < n; a++) { parent[a] = -1; seen[a] = false; }
seen[0] = true;
var stack = [0];
while (stack.length > 0) {
var w = stack.pop();
order.push(w);
for (var j2 = 0; j2 < adj[w].length; j2++) { var y = adj[w][j2]; if (!seen[y]) { seen[y] = true; parent[y] = w; stack.push(y); } }
}
var full = [], half = [];
for (var b = 0; b < n; b++) { full.push(cnt[b] * price[b]); half.push(cnt[b] * price[b] / 2); }
for (var p = n - 1; p >= 0; p--) {
var z = order[p], pz = parent[z];
if (pz >= 0) { full[pz] += Math.min(full[z], half[z]); half[pz] += full[z]; }
}
return Math.min(full[0], half[0]);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming