[Python] Strict O(n) Solution
Intuition\nOnly the ancestors of value 1 and itself has miss value >1.\nThat is the path from root 0 to the node with value 1.\nSo we only need to handle nodes 
# **Intuition**\nOnly the ancestors of value 1 and itself has miss value >1.\nThat is the path from root 0 to the node with value 1.\nSo we only need to handle nodes on this path.\n<br>\n\n# **Complexity**\nTime `O(n)`\nSpace `O(n)`\n<br>\n\n**Java**\nslightly changed from @deepli\n```java\n    HashMap<Integer, List<Integer>> m = new HashMap<>();\n    int[] A;\n    int miss = 1;\n    HashSet<Integer> set = new HashSet<>();\n\n    public int[] smallestMissingValueSubtree(int[] parent, int[] nums) {\n\n        int n = parent.length;\n        A = nums;\n        for (int i = 0; i < n; i++) {\n            m.computeIfAbsent(parent[i], k->new ArrayList<>()).add(i);\n        }\n        int[] res = new int[n];\n        Arrays.fill(res, 1);\n        int idx = -1;\n        for (int i = 0; i < n; i++) {\n            if (nums[i] == 1) {\n                idx = i;\n                break;\n            }\n        }\n        if (idx == -1) return res;\n        int s = idx;\n        int pre = -1; // pre handled node\n        while (s != -1) {\n            List<Integer> list = m.get(s);\n            if (list != null) {\n                for (int j : m.get(s)) {\n                    if (j == pre)  continue; // skip handled\n                    dfs(j);\n                }\n            }\n            set.add(A[s]);\n            while (set.contains(miss)) {\n                miss++;\n            }\n            res[s] = miss;\n\n            pre = s; // update pre and s\n            s = parent[s]; // path from 1 up to root\n\n        }\n        return res;\n    }\n\n    void dfs(int i) {\n        set.add(A[i]);\n        List<Integer> list = m.get(i);\n        if (list == null) return;\n        for (int j : list) {\n            dfs(j);\n        }\n    }\n```\n**C++**\nslightly changed from @chandanagrawal23\n```cpp\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& val) {\n        int n = parents.size();\n        vector<int>res(n, 1), seen(100010, 0);\n        auto it = find(val.begin(), val.end(), 1);\n        if (it == val.end()) return res;\n        vector<int>children[n];\n        for (int i = 1; i < n; i++)\n            children[parents[i]].push_back(i);\n        int i = it - val.begin(), miss = 1;\n        while (i > -1) {\n            dfs(i, children, seen, val);\n            while (seen[miss])\n                miss++;\n            res[i] = miss;\n            i = parents[i];\n        }\n        return res;\n    }\n\n    void dfs(int i, vector<int>children[], vector<bool>&seen, vector<int>&val) {\n        if (seen[val[i]]) return;\n        for (int& j : children[i])\n            dfs(j, children, seen, val);\n        seen[val[i]] = 1;\n    }\n```\n**Python**\n```py\n    def smallestMissingValueSubtree(self, parents, nums):\n        n = len(parents)\n        res = [1] * n\n        seen = [0] * 100010\n        if 1 not in nums:\n            return res\n        children = [[] for i in xrange(n)]\n        for i in xrange(1, n):\n            children[parents[i]].append(i)\n\n        def dfs(i):\n            if seen[nums[i]] == 0:\n                for j in children[i]:\n                    dfs(j)\n                seen[nums[i]] = 1\n\n        i = nums.index(1)\n        miss = 1\n        while i >= 0:\n            dfs(i)\n            while seen[miss]:\n                miss += 1\n            res[i] = miss\n            i = parents[i]\n        return res\n```\n
[]