Maximum subgraph score in a tree

Array Dynamic Programming Tree Depth-First Search

70.5% acceptance

Feb 25, 2026

You are given an undirected tree with n nodes, numbered from 0 to n - 1. It is represented by 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. You are also given an integer array good of length n, where good[i] is 1 if the ith node is good, and 0 if it is bad. Define the score of a subgraph as the number of good nodes minus the number of bad nodes in that subgraph. For each node i, find the maximum possible score among all connected subgraphs that contain node i. Return an array of n integers where the ith element is the maximum score for node i. A subgraph is a graph whose vertices and edges are subsets of the original graph. A connected subgraph is a subgraph in which every pair of its vertices is reachable from one another using only its edges.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_subgraph_score(n: i32, edges: Vec<Vec<i32>>, good: Vec<i32>) -> Vec<i32> {
    let n = n as usize;
    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 val: Vec<i32> = good.iter().map(|&g| 2 * g - 1).collect();

    // down[v] = max score of connected subgraph in subtree of v containing v
    let mut down = vec![0i32; n];
    let mut parent = vec![n; n];
    // BFS order
    let mut order = Vec::with_capacity(n);
    let mut visited = vec![false; n];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(0usize);
    visited[0] = true;
    while let Some(u) = queue.pop_front() {
      order.push(u);
      for &v in &adj[u] {
        if !visited[v] {
          visited[v] = true;
          parent[v] = u;
          queue.push_back(v);
        }
      }
    }
    // Compute down bottom-up
    for &u in order.iter().rev() {
      down[u] = val[u];
      for &v in &adj[u] {
        if v != parent[u] {
          let contrib = down[v].max(0);
          down[u] += contrib;
        }
      }
    }
    // Rerooting: ans[v] = max score including v from all directions
    let mut ans = vec![0i32; n];
    let mut from_above = vec![0i32; n]; // contribution from parent's side
    ans[0] = down[0];
    for &u in &order {
      let children: Vec<usize> = adj[u].iter().cloned().filter(|&v| v != parent[u]).collect();
      // For each child c, compute what u contributes excluding c
      // down_excl_c[u] = val[u] + from_above[u] + sum of max(0, down[v]) for v != c
      let sum_children: i32 = children.iter().map(|&c| down[c].max(0)).sum();
      for &c in &children {
        let excl = val[u] + from_above[u] + sum_children - down[c].max(0);
        from_above[c] = excl.max(0);
        let child_ans = from_above[c] + down[c];
        ans[c] = child_ans;
      }
    }
    ans
  }
}