Minimize the total price of the trips

Array Dynamic Programming Tree Depth-First Search Graph Theory

47.9% acceptance

Feb 25, 2026

517

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

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_total_price(n: i32, edges: Vec<Vec<i32>>, price: Vec<i32>, trips: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      adj[e[0] as usize].push(e[1] as usize);
      adj[e[1] as usize].push(e[0] as usize);
    }

    // Count how many times each node is visited across all trips
    let mut count = vec![0i32; n];

    // DFS to find path from src to dst, increment count for nodes on path
    fn find_path(adj: &Vec<Vec<usize>>, src: usize, dst: usize, count: &mut Vec<i32>) -> bool {
      if src == dst {
        count[src] += 1;
        return true;
      }
      // We need to do DFS with parent tracking
      fn dfs(adj: &Vec<Vec<usize>>, u: usize, parent: usize, dst: usize, count: &mut Vec<i32>) -> bool {
        if u == dst {
          count[u] += 1;
          return true;
        }
        for &v in &adj[u] {
          if v == parent { continue; }
          if dfs(adj, v, u, dst, count) {
            count[u] += 1;
            return true;
          }
        }
        false
      }
      dfs(adj, src, usize::MAX, dst, count)
    }

    for trip in &trips {
      find_path(&adj, trip[0] as usize, trip[1] as usize, &mut count);
    }

    // Tree DP: returns (not_halved, halved)
    fn dp(adj: &Vec<Vec<usize>>, u: usize, parent: usize, price: &Vec<i32>, count: &Vec<i32>) -> (i64, i64) {
      let base = count[u] as i64 * price[u] as i64;
      let mut not_halved = base;
      let mut halved = base / 2;

      for &v in &adj[u] {
        if v == parent { continue; }
        let (ch_not, ch_halved) = dp(adj, v, u, price, count);
        not_halved += ch_not.min(ch_halved);
        halved += ch_not; // if u is halved, children cannot be halved
      }
      (not_halved, halved)
    }

    let (a, b) = dp(&adj, 0, usize::MAX, &price, &count);
    a.min(b) as i32
  }
}