Create components with same value

Array Math Tree Depth-First Search Enumeration

53.3% acceptance

Feb 25, 2026

439

There is an undirected tree with n nodes labeled from 0 to n - 1. You are given a 0-indexed integer array nums of length n where nums[i] repres ents the value of the ith node. You are also 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. * You are allowed to delete some edges, splitting the tree into multiple connec ted components. Let the value of a component be the sum of all nums[i] for which node i is in the component. * Return the maximum number of edges you can delete, such that every connected component in the tree has the same value. *

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn component_value(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
    let n = nums.len();
    let total: i32 = nums.iter().sum();
    let mut adj = 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);
    }

    fn dfs(node: usize, parent: usize, nums: &[i32], adj: &Vec<Vec<usize>>, target: i32) -> (i32, bool) {
      let mut sum = nums[node];
      for &nb in &adj[node] {
        if nb == parent { continue; }
        let (child_sum, ok) = dfs(nb, node, nums, adj, target);
        if !ok { return (0, false); }
        sum += child_sum;
      }
      if sum > target { return (0, false); }
      if sum == target { return (0, true); }
      (sum, true)
    }

    for k in (1..=n as i32).rev() {
      if total % k != 0 { continue; }
      let target = total / k;
      let (_, ok) = dfs(0, n, &nums, &adj, target);
      if ok { return k - 1; }
    }
    0
  }
}