Maximum score after applying operations on a tree

Dynamic Programming Tree Depth-First Search

47.1% acceptance

Feb 25, 2026

366

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]. You are also given a 0-indexed integer array values of length n. You start with a score of 0. In one operation, you can pick any node i, add values[i] to score, set values[i] to 0. A tree is healthy if the sum of values on the path from the root to any leaf node is different than zero. Return the maximum score you can obtain after performing operations so that the tree remains healthy.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_score_after_operations(edges: Vec<Vec<i32>>, values: Vec<i32>) -> i64 {
    let n = values.len();
    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);
    }
    let total: i64 = values.iter().map(|&v| v as i64).sum();

    // dp(node, parent) = min sum to keep in subtree of node so all paths to leaves stay nonzero
    fn dfs(node: usize, parent: usize, adj: &Vec<Vec<usize>>, values: &Vec<i32>) -> i64 {
      let children: Vec<usize> = adj[node].iter().copied().filter(|&c| c != parent).collect();
      if children.is_empty() {
        // leaf: must keep this node
        return values[node] as i64;
      }
      let sum_children: i64 = children.iter().map(|&c| dfs(c, node, adj, values)).sum();
      (values[node] as i64).min(sum_children)
    }

    let keep = dfs(0, usize::MAX, &adj, &values);
    total - keep
  }
}