Most profitable path in a tree

Array Tree Depth-First Search Breadth-First Search Graph Theory

67.3% acceptance

Feb 25, 2026

1399

245

There is an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. You are given 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. At every node i, there is a gate. You are also given an array of even integers amount, where amount[i] represents the price needed (if negative) or cash reward (if non-negative) on opening the gate. Alice is at node 0, Bob is at node bob. Each second they both move to an adjacent node. Alice moves towards some leaf node, Bob moves towards node 0. If they reach a node simultaneously, they share the price/reward (amount[i]/2 each). Return the maximum net income Alice can have.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn most_profitable_path(edges: Vec<Vec<i32>>, bob: i32, amount: Vec<i32>) -> i32 {
    let n = amount.len();
    let mut adj: Vec<Vec<usize>> = 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);
    }
    let bob = bob as usize;

    // Find Bob's path timing using DFS with backtracking
    let mut bob_time = vec![i32::MAX; n];
    fn dfs_bob(
      u: usize, par: usize, t: i32,
      adj: &Vec<Vec<usize>>, bt: &mut Vec<i32>,
    ) -> bool {
      bt[u] = t;
      if u == 0 { return true; }
      for &v in &adj[u] {
        if v != par && dfs_bob(v, u, t + 1, adj, bt) { return true; }
      }
      bt[u] = i32::MAX;
      false
    }
    dfs_bob(bob, n, 0, &adj, &mut bob_time);

    // Alice DFS - maximize income along root-to-leaf path
    let mut best = i32::MIN;
    fn dfs_alice(
      u: usize, par: usize, t: i32, inc: i32,
      adj: &Vec<Vec<usize>>, bt: &Vec<i32>, amount: &Vec<i32>, best: &mut i32,
    ) {
      let gain = if t < bt[u] { amount[u] } else if t == bt[u] { amount[u] / 2 } else { 0 };
      let inc = inc + gain;
      let mut leaf = true;
      for &v in &adj[u] {
        if v != par {
          leaf = false;
          dfs_alice(v, u, t + 1, inc, adj, bt, amount, best);
        }
      }
      if leaf { *best = (*best).max(inc); }
    }
    dfs_alice(0, n, 0, 0, &adj, &bob_time, &amount, &mut best);
    best
  }
}