Choose edges to maximize score in a tree

Dynamic Programming Tree Depth-First Search

56.5% acceptance

Mar 31, 2026

You are given a weighted tree consisting of n nodes numbered from 0 to n - 1. The tree is rooted at node 0 and represented with a 2D array edges of size n where edges[i] = [pari, weighti] indicates that node pari is the parent of node i, and the edge between them has a weight equal to weighti. Since the root does not have a parent, you have edges[0] = [-1, -1]. Choose some edges from the tree such that no two chosen edges are adjacent and the sum of the weights of the chosen edges is maximized. Return the maximum sum of the chosen edges. Note: You are allowed to not choose any edges in the tree, the sum of weights in this case will be 0. Two edges Edge1 and Edge2 in the tree are adjacent if they have a common node. In other words, they are adjacent if Edge1 connects nodes a and b and Edge2 connects nodes b and c.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(edges: Vec<Vec<i32>>) -> i64 {
    let n = edges.len();
    // Build children list
    let mut children = vec![vec![]; n];
    for i in 1..n {
      let parent = edges[i][0] as usize;
      let weight = edges[i][1] as i64;
      children[parent].push((i, weight));
    }
    
    // DFS: returns (not_picked, picked)
    // not_picked: max score in subtree of node when edge from parent to node is NOT picked
    // picked: max score in subtree of node when edge from parent to node IS picked
    fn dfs(node: usize, children: &Vec<Vec<(usize, i64)>>) -> (i64, i64) {
      // Base sum: sum of not_picked for all children (no child edge picked)
      let mut base = 0i64;
      let mut child_results: Vec<(i64, i64, i64)> = Vec::new(); // (not_picked, picked, weight)
      
      for &(child, weight) in &children[node] {
        let (np, p) = dfs(child, children);
        base += np;
        child_results.push((np, p, weight));
      }
      
      // not_picked: parent edge not picked, so we can pick at most one child edge
      // Try picking each child edge and see which gives max gain
      let mut best_gain = 0i64;
      for &(np, p, w) in &child_results {
        let gain = p + w - np;
        best_gain = best_gain.max(gain);
      }
      let not_picked = base + best_gain;
      
      // picked: parent edge is picked, so no child edge can be picked
      let picked = base;
      
      (not_picked, picked)
    }
    
    let (result, _) = dfs(0, &children);
    result
  }
}