Union-Find with thinking process + A Bonus Variant!
Here is a naive approach:\n\n1. For each node i, do dfs and return a set of genetic values included in the subtree below i.\n2. Do a linear search of ans[i] by 
Here is a naive approach:\n\n1. For each node i, do dfs and return a set of genetic values included in the subtree below i.\n2. Do a linear search of ans[i] by checking whether a is in dfs(i), and if yes a++. (A simple trick: ans[parent]>=ans[child] for every child of parent. So we can start checking from the maximum of ans[children].)\n\nTo implement this idea, suppose we know dfs(ch) for each child of p=parent, what is dfs(p) ? Well, clearly it\'s the union of {nums[p]} and {dfs(ch) for ch in children of p}.\nThe union of sets are clearly the bottleneck of the algorithm. If the possible values in nums are small, we may use bitmask to represent the HashSet, however 1e5 is too large.\nWhat if we only use one set of genetic values? The problem is if we are visiting two disjoint branches, we cannot tell whether a genetic value is from another visited branch or the current subtree [**Update: It turns out this can be done as illustrated by better posts in discussion! Because there is only one branch that contains 1, and all other ones should return 1, therefore as long as we visit the branch with 1 at first, there is no problem, as the other branches don\'t even need to know what they contain since they already miss 1.**]. So we have to union things. How to efficiently take union of things? The Union-Find data structure! Hence the following efficient algorithm:\n\n1. For each node, do dfs and return nothing but set ans[i] to be correct at the end of the visit.\n2. After visiting each ch=child of node p, we make sure find(ch) to be p, therefore we have a way to know whether a genetic value is from the current subtree or a disjoint branch.\n\nPython3 codes:\n\n```\nclass Solution:\n    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n        \n        n = len(parents)\n        G = [[] for _ in range(n)] # G[i] is the list of children of i.\n        for i, p in enumerate(parents):\n            if p!=-1: G[p].append(i)\n        \n        ans = [1]*n # the array to be returned\n        num2node = {}\n        \n        def find(i):\n            while parents[i]!=i: # reuse parents as the underlying union-find structure\n                parents[i] = parents[parents[i]]\n                i = parents[i]\n            return i\n        \n        def dfs(p):\n            num2node[nums[p]] = p\n            parents[p] = p\n            a = 1\n            for ch in G[p]:\n                dfs(ch)\n                a = max(a, ans[ch])\n                parents[ch] = p # "union"\n            while a in num2node and find(num2node[a])==p: a += 1\n            ans[p] = a\n        \n        dfs(0)\n        return ans\n ```\n\n **Update: A Bonus Variant** \n \nI found a more challenging variant of the problem ("The First Hole in the values of the subtree") that makes this algorithm more useful: still assume all genetic values are distinct, but return ans[i] to be the minimal positive integer that is missing from the subtree of i and **BIGGER THAN AT LEAST ONE GENETIC VALUE IN THE SUBTREE**.  For example, if a substree contains genetic values {3, 4, 6, 7}, then the answer for it should be 5 instead of 1. A simple two line change of the above codes (named lessEffi in the codes below) works but is not efficient, as search from min of children might repeat.\n\nNow to improve the efficiency, note that we search a in the subtree of i iff a-1 is included in the substree. Therefore, for parallel branches, there is no need to repeat, so we may record the search by an array NEXT; \n\nIs there still a better trick for this problem?\n\n<iframe src="https://leetcode.com/playground/AvApCU2B/shared" frameBorder="0" width="800" height="500"></iframe>
[]