[Java] O(n) using Time Stamps for Trees, Comprehensively Explained
Basic Ideas:\n1. Denote the least missing descendant for some node N as \'rem\', then all positive integers smaller than \'rem\' has to have N as the ancestor.\
Basic Ideas:\n1. Denote the least missing descendant for some node ***N*** as **\'rem\'**, then all positive integers smaller than ***\'rem\'*** has to have ***N*** as the ancestor.\n2. We use **dfs** to find the least missing descendent for all ***N***\'s children. Suppose **N** has **c** children, denote their least missing descendant as **lost = {a1, a2, a3... ac}**, then sort **lost**, and try to find if **ai** is a descendent of **N**. If some ai is not, then ***\'rem\'*** = **ai**. Otherwise, keep **adding 1 to \'rem\'** until **\'rem\'** is not a descendant of **N**.\n3. In the worst case scenario, **\'rem\'** of any node can be as large as 100001. Thus, we check if **ai** is a descendant of an arbitrary **N** at most 200002 times (if ai is not a descendant of **N** (false answer), we just set **\'rem\'** as **ai**, thus there\'s at most 1 false answer for each **N**, and no more subsequent checks are made. For true answers(**ai** is a descendant of **N**), any other descendant check on **ai** will be a false answer (**ai** will not be checked for any ancestor of **N** (dfs property), and for the rest of the nodes, since **ai** is a descendant of **N**, it won\'t be a descendant for those other nodes.) So in total, at most 100001(false) +1000001 (true) checks are performed in the whole dfs).\n4. As a result, if each of our checks can be O(1), we limit our time complexity to strictly O(n).\n5. To achieve this, imagine you are traversing through the tree using inorder traversal (left subtree->root->right subtree). It takes 1 second for you to go to another node, and stay 1 second on each node. Whenever you walk into (start traversal on the node) and out (finish traversal on the node) of a node you record current time. You\'ll find out that if node **N1** is node **N2**\'s ancestor, you first arrive at **N1** earlier than **N2**, and you leave **N1** later than **N2** (that follows from the path you took, you can draw a tree to understand better). On the other hand, if neither is the other\'s ancestor, then the two time intervals ([arrival, departure]) won\'t have overlap at all. So if we record the arrival and departure time for each node, we can determine if one\'s another\'s ancestor in O(1) using the above tools (implemented in dfs2).\n```\nclass Solution {\n    HashMap<Integer, HashSet<Integer>> map;\n    int[] nums;\n    int[] res;\n    public class Pair{\n        int m;\n        int sz;\n        public Pair(int ap, int cp){\n            m=ap;\n            sz=cp;\n        }\n    }\n    public Pair dfs(int cur){\n        HashSet<Integer> set = map.get(cur);\n        int val = nums[cur];\n        int[] vt = times[val];\n        if(set.isEmpty()){\n            res[cur]=val==1?2:1;\n            return new Pair(val==1?2:1,1);\n        }\n        if(set.size()==1){\n            for(int ele : set){\n                Pair p = dfs(ele);\n                int rem = p.m;\n                while(times[rem][0]>=vt[0]&&times[rem][1]<=vt[1]){\n                    ++rem;\n                }\n                res[cur]=rem;\n                return new Pair(rem,p.sz+1);\n            }\n        }\n        int sss = set.size();\n        Pair[] l = new Pair[sss];\n        int ii=0;\n        for(int ele : set){\n            Pair p = dfs(ele);\n            l[ii]=p;\n            ++ii;\n        }\n        int[] lost = new int[sss];\n        int tot_sz = 0;\n        for(int i=0;i<sss;++i){\n            Pair p = l[i];\n            tot_sz+=p.sz;\n            lost[i]=p.m;\n        }\n        Arrays.sort(lost);\n        int rem = lost[0];\n        int ind = 1;\n        int len = sss;\n        while(times[rem][0]>=vt[0]&&times[rem][1]<=vt[1]){\n            if(ind==len){\n                break;\n            }\n            rem=lost[ind];\n            ++ind;\n        }\n        while(ind==len&&times[rem][0]>=vt[0]&&times[rem][1]<=vt[1]){\n            ++rem;\n        }\n        res[cur]=rem;\n        return new Pair(rem,tot_sz+1);\n    }\n    int[][] times = new int[100002][2];\n    int time;\n    public void dfs2(int cur){\n        int val = nums[cur];\n        HashSet<Integer> set = map.get(cur);\n        int st = time;\n        for(int ele : set){\n            ++time;\n            dfs2(ele);\n        }\n        ++time;\n        int end=time;\n        times[val][0]=st;\n        times[val][1]=end;\n    }\n    public int[] smallestMissingValueSubtree(int[] p, int[] nums) {\n        time=0;\n        map = new HashMap<>();\n        for(int i=0;i<=100001;++i){\n            Arrays.fill(times[i],-1);\n        }\n        this.nums=nums;\n        res = new int[nums.length];\n        for(int i=0;i<=nums.length;++i){\n            map.put(i,new HashSet<>());\n        }\n        for(int i=1;i<p.length;++i){\n            map.get(p[i]).add(i);\n        }\n        dfs2(0);\n        dfs(0);\n        return res;\n    }\n}\n```
[]