Python [recursion on a bit set]
First we put everything in the usual directed graph form in the adjacency matrix graph.\n\nWhen we are on a leaf, it\'s simple. The answer is 1 if nums[i] > 1 a
First we put everything in the usual directed graph form in the adjacency matrix `graph`.\n\nWhen we are on a leaf, it\'s simple. The answer is `1` if `nums[i] > 1` and `2` otherwise. How do we proceed upwards?\n\nFor each descendant, we can keep track of the genetic numbers seen. We can do this in a single variable using a bit set (ret). Also, for each descendant we can keep track of the min index we started from seaching (cmin) to avoid time waste.\n\nWith this form the answer is AC. I have also tried using a regular set but that one got TLE.\n\n```python\nclass Solution:\n    def smallestMissingValueSubtree(self, parents, nums):\n        n = len(parents)\n        \n        graph = [[] for _ in range(n)]\n        for i, j in enumerate(parents):\n            if j != -1:\n                graph[j].append(i)\n\n        def recur(i):\n            #LEAF NODE\n            if not graph[i]: \n                ret = 0\n                x = nums[i]\n                ret += (1<<x)\n                cmin = 1 if x > 1 else 2\n                ans[i] = cmin\n                return ret, cmin\n            \n            #NOT LEAF NODE\n            ret, cmin = 0, 1\n            for j in graph[i]:\n                tret, tcmin = recur(j)\n                ret += tret\n                cmin = max(cmin, tcmin)\n            x = nums[i]\n            ret += (1<<x)\n            \n            while (ret >> cmin) & 1:\n                cmin += 1\n            ans[i] = cmin\n            return ret, cmin\n\n        \n        ans = [0] * n    \n        recur(0)\n        return ans\n```
[]