[Simple & Efficient] Parent Traversal & DFS & Vector Set - O(n)
Algorithm\n\n1) All nodes except those on the path from the root to the 1-node are ones.\n2) The nodes on the path have minimum values from { 1...n+1 } / { gene
**Algorithm**\n\n1) All nodes except those on the path from the `root` to the `1-node` are `ones`.\n2) The nodes on the `path` have minimum values from `{ 1...n+1 } / { genetic values of these nodes and their children}`.\n\n**Finding Minimum Values**\n1) Use an ordered set. *O(nlogn)*\n2) Use a boolean vector. *O(n)*\n\ta) Marking a value as used is *O(1)*.\n\tb) Finding the next minimum value is *O(n)*, but the overall complexity of all searches is also *O(n)*, as we always search from the last position.\n\n**Complexity**\n1) DFS is *O(n)*.\n2) Finding all required Minimum Values is *O(n)*.\n3) All other operations are also *O(n)*\n\nOverall complexity is **O(n)**.\n\n```\nclass Solution {\n    \n    vector<vector<int>> tree;\n    vector<bool> left;\n    \n    void remove(int p, int s, vector<int> &nums) {\n        if (nums[p] < left.size())\n            left[nums[p]] = true;\n        for (int d : tree[p])\n            if (d != s)\n                remove(d, s, nums);\n    }\n    \npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size(), p = 0, current = 1;\n        vector<int> res(n, 1);\n        for (; p < n && nums[p] != 1; ++p);\n        if (p < n) {\n            tree.resize(n);\n            left.resize(n + 2, false);\n            for (int i = 1; i < n; ++i)\n                tree[parents[i]].push_back(i);\n            for (int s = -1; p != -1; s = p, p = parents[p]) {\n                remove(p, s, nums);\n                for (; current < left.size() && left[current]; ++current);\n                res[p] = current;\n            }\n        }\n        return res;\n    }\n};\n```\nPlease upvote if you liked the explanation or ask for clarification in comments.
['C']