Beats 100% on runtime [EXPLAINED]
Intuition\nA family tree where each node represents a person with a unique genetic value. We need to find the smallest genetic value that is missing in the subt
# Intuition\nA family tree where each node represents a person with a unique genetic value. We need to find the smallest genetic value that is missing in the subtree for each node, considering all its descendants.\n\n# Approach\nWe build the family tree using a graph structure, identify the node with genetic value 1, traverse up the tree while marking all genetic values seen in each node\u2019s subtree, and then determine the smallest missing value for each node based on these markings.\n\n# Complexity\n- Time complexity:\nO(n), where n is the number of nodes, since each node is processed once.\n\n- Space complexity:\nO(1) for the seen array (fixed size) and O(n) for the graph representation, which is acceptable within the problem\'s constraints.\n\n# Code\n```python3 []\nclass Solution:\n    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n        n = len(parents)\n        graph = defaultdict(list)\n        node_one = None\n\n        # Build the tree structure and find the root and node with genetic value 1\n        for child, parent in enumerate(parents):\n            if parent == -1:\n                root = child  # Root node identified\n            else:\n                graph[parent].append(child)\n            if nums[child] == 1:\n                node_one = child  # Node with genetic value 1 found\n\n        # Initialize results and seen values\n        results = [1] * n\n        if node_one is None:\n            return results  # Return early if there is no node with genetic value 1\n\n        seen = [False] * 100002  # Boolean array to track seen genetic values\n        current_node = node_one\n        previous_missing = 1\n\n        # Traverse upwards from the node with genetic value 1\n        while current_node != -1:\n            self._markSeen(current_node, graph, seen, nums)\n            # Find the first missing genetic value\n            while previous_missing < 100002 and seen[previous_missing]:\n                previous_missing += 1\n            results[current_node] = previous_missing  # Assign the missing value\n            current_node = parents[current_node]  # Move to the parent node\n\n        return results\n\n    def _markSeen(self, node: int, graph: defaultdict, seen: List[bool], nums: List[int]):\n        """DFS to mark genetic values seen in the subtree rooted at \'node\'."""\n        if not seen[nums[node]]:\n            seen[nums[node]] = True  # Mark the current node\'s genetic value as seen\n            for child in graph[node]:\n                self._markSeen(child, graph, seen, nums)  # Recursively mark children\n\n```
['Python3']