Minimize the Total Price of the Trips

Hard
1710.

Minimize the Total Price of the Trips

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.

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 <= 50
  • edges.length == n - 1
  • 0 <= a, b <= n - 1
  • edges represents a valid tree
  • price.length == n
  • price[i] is even
  • 1 <= price[i] <= 1000
  • 1 <= trips.length <= 100
  • 0 <= start, end <= n - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[]} price
 * @param {number[][]} trips
 * @return {number}
 */
var minimumTotalPrice = function(n, edges, price, trips) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 50
  • edges.length == n - 1
  • 0 <= a, b <= n - 1
  • edges represents a valid tree
  • price.length == n
  • price[i] is even
  • 1 <= price[i] <= 1000
  • 1 <= trips.length <= 100
  • 0 <= start, end <= n - 1

Hints for Minimize the Total Price of the Trips

  1. 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 · price in full or count · price / 2 when halved.

  2. 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.

  3. 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

  1. For each trip, find parents by a DFS/BFS from start and walk back from end, adding 1 to cnt of every node on the path.
  2. Root the tree at 0. Process nodes children-first and keep full[v] (v keeps its price) and half[v] (v is halved).
  3. full[v] = cnt[v]·price[v] + Σ min(full[c], half[c]) and half[v] = cnt[v]·price[v]/2 + Σ full[c] over the children c.
  4. 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