# 1273. Delete Tree Nodes
A tree rooted at node 0 is given as follows:
The number of nodes is nodes; The value of the i-th node is value[i]; The parent of the i-th node is parent[i]. Remove every subtree whose sum of values of nodes is zero.
After doing so, return the number of nodes remaining in the tree.
Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1] Output: 2
Approach 1: DFS after reconstructing the tree.
Approach 2: assuming the params are given top down (numbering the nodes from root to leaf in level order), can go through the array without reconstructing the tree.
# Code (Python)
import collections class Solution: def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int: if not nodes: return 0 children = collections.defaultdict(list) for i, val in enumerate(parent): children[val].append(i) root = children.pop(-1) return self._recurse(root, children, value) def _recurse(self, node, children, value): # return (sum, num of undeleted nodes in subtree including self) total = value[node] count = 1 for child in children[node]: child_total, child_count = self._recurse(child, children, value) total += child_total count += child_count if total == 0: return (0, 0) return (total, count)
def deleteTreeNodes(self, n: int, parent: List[int], value: List[int]) -> int: # Without reconstructing the tree. This assumes the params are given top down (numbering the nodes from root to leaf in level order) if n == 1: return 0 if value == 0 else 1 res =  * n for i in range(n - 1, 0, -1): value[parent[i]] += value[i] res[parent[i]] += res[i] if value[i] else 0 return res
# Code (C++)