Py/Rust DFS and try all divisors with detailed explanation
Intuition\n\nFirst you can find the sum of all values in the tree and lets assume it is s, then potentially you can try to split a tree into every divisor of s.
# Intuition\n\nFirst you can find the sum of all values in the tree and lets assume it is `s`, then potentially you can try to split a tree into every divisor of `s`. If this divisor is `d` and you can divide into them, then the number of cuts will be `s / d - 1`. So you try from the smallest divisor to the latest one and if you can divide, return that number of cuts.\n\nNow the question is narrowed down to: You have a tree and whether it is possible to cut it into chunks where each of them has sum of nodes equal to `d`. There are might be multiple approaches to do it, but an easy approach is to use DFS.\n\nIn dfs you need to keep track your current node, your previous node (to not run dfs on nodes you already ran) and sum you need to achieve. And inside of it you maintain your own sum. If the sum becomes equal to divisor, we can make a cut and the sum becomes zero. \n\nIn the end if the sum is not equal to 0, it means you can\'t divide them into chunks. One improvement you can do is do short-cirquit if sum becomes > divisor (I do not do it, but this can trim fast).\n\n# Complexity\n\nLet $k$ be the number of divisors of the sum. Based on my understanding [from this page](https://en.wikipedia.org/wiki/Divisor_function) on average it grows roughly logarithmic. As the sum is bounded by 50 * n, the complexity will not be high.\n\n- Time complexity: $O(n \\cdot k)$\n- Space complexity: $O(n)$\n\n# Code\n```Python []\nclass Solution:\n\n  def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n    def dfs(node_curr, node_prev, num):\n      res = nums[node_curr]\n\n      for node_next in tree[node_curr]:\n        if node_prev == node_next:\n          continue\n\n        res += dfs(node_next, node_curr, num)\n\n      return res if res != num else 0\n\n    tree, s = [[] for _ in range(len(edges) + 1)], sum(nums)\n    for v1, v2 in edges:\n      tree[v1].append(v2)\n      tree[v2].append(v1)\n\n    for i in range(1, s + 1):\n      if s % i == 0 and dfs(0, -1, i) == 0:\n        return s // i - 1\n\n    return 0\n```\n```Rust []\nimpl Solution {\n\n  fn dfs(tree: &Vec<Vec<usize>>, nums: &Vec<i32>, node_curr: usize, node_prev: usize, s: i32) -> i32 {\n    let mut res = nums[node_curr];\n    for i in 0 .. tree[node_curr].len() {\n      let node_next = tree[node_curr][i];\n      if node_next == node_prev {\n        continue;\n      }\n\n      res += Self::dfs(tree, nums, node_next, node_curr, s);\n    }\n\n    if res == s {\n      return 0;\n    }\n    return res;\n  }\n\n  pub fn component_value(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {\n    let s = nums.iter().sum::<i32>();\n    let mut tree = vec![Vec::new(); nums.len() + 1];\n    for e in edges {\n      tree[e[0] as usize].push(e[1] as usize);\n      tree[e[1] as usize].push(e[0] as usize);\n    }\n\n    for i in 1 ..= s {\n      if s % i == 0 && Self::dfs(&tree, &nums, 0, usize::MAX, i) == 0 {\n        return s / i - 1;\n      }\n    }\n\n    return 0;\n  }\n}\n```
['Python', 'Rust']