Difference between maximum and minimum price sum

Array Dynamic Programming Tree Depth-First Search

33.2% acceptance

Feb 25, 2026

476

There exists an undirected and initially 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. The tree can be rooted at any node root of your choice. The incurred cost after choosing root is the difference between the maximum and minimum price sum amongst all paths starting at root. Return the maximum possible cost amongst all possible root choices.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_output(n: i32, edges: Vec<Vec<i32>>, price: Vec<i32>) -> i64 {
    let n = n as usize;
    let price: Vec<i64> = price.iter().map(|&x| x as i64).collect();
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u].push(v);
      adj[v].push(u);
    }

    // dp[u] = max path sum from u into its subtree (including u)
    let mut dp = vec![0i64; n];
    // dp2[u] = max path sum from u going through parent (including u)
    let mut dp2 = vec![0i64; n];
    let mut par = vec![usize::MAX; n];
    let mut order = Vec::with_capacity(n);

    // Iterative DFS (avoid stack overflow on deep trees)
    let mut stack = vec![(0usize, usize::MAX)];
    while let Some((u, p)) = stack.pop() {
      par[u] = p;
      order.push(u);
      for &v in &adj[u] {
        if v != p {
          stack.push((v, u));
        }
      }
    }

    // Post-order: compute dp[u]
    for &u in order.iter().rev() {
      dp[u] = price[u];
      for &v in &adj[u] {
        if v != par[u] {
          dp[u] = dp[u].max(price[u] + dp[v]);
        }
      }
    }

    // Pre-order: compute dp2 and answer
    dp2[0] = price[0];
    let mut ans = 0i64;

    for &u in order.iter() {
      // cost(u) = max_path_from_u - price[u]
      ans = ans.max(dp[u].max(dp2[u]) - price[u]);

      // Compute dp2 for children of u
      // Track top-2 dp values among u's children
      let mut top1 = 0i64;
      let mut top2 = 0i64;
      for &v in &adj[u] {
        if v != par[u] {
          let val = dp[v];
          if val >= top1 {
            top2 = top1;
            top1 = val;
          } else if val > top2 {
            top2 = val;
          }
        }
      }

      for &v in &adj[u] {
        if v != par[u] {
          let best_sibling = if dp[v] == top1 { top2 } else { top1 };
          let up_from_u = dp2[u].max(price[u] + best_sibling);
          dp2[v] = price[v] + up_from_u;
        }
      }
    }

    ans
  }
}