[C++][BFS] Short and simple O(n) with comments
\nclass Solution {\npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size(), id = 0;\n  
```\nclass Solution {\npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size(), id = 0;\n        while (id < n && nums[id] != 1) id++;\n\t\t// initially the answer for all nodes is 1\n        vector<int> ans(n, 1);\n\t\t// if there is no node with 1 the answer is all 1s\n        if (id == n) return ans;\n        \n        vector<vector<int> > ady(n);\n        for(int i=1;i<n;i++) ady[ parents[i] ].push_back(i);\n        \n        vector<bool> used(100005);\n        int next = 1, prev = -1;\n\t\t// we only need to traverse the path to the root from the node that contains the 1\n        while (id != -1) {\n\t\t    // we need to mark all the numbers included in the current subtree, avoiding the previous visited subtree\n            used[nums[id]] = true;\n            for(int &v : ady[id]) \n                if (v != prev)\n                    bfs(v, ady, used, nums);\n\t\t    // we calculate the answer for the current node\n\t\t\t// the smallest number that is not marked\n            while (used[next]) next++;\n            ans[id] = next; // update the answer for the current node\n            \n            prev = id; // keep the current node to avoid traverse his subtree in the next iteration\n            id = parents[id]; // change for the next node, the parent of the current node\n        }\n        return ans;\n    }\n    \n    void bfs(int root, vector<vector<int> > &ady, vector<bool> &used, vector<int>& nums) {\n        queue<int> q;\n        q.push(root);\n        while (!q.empty()) {\n            int v = q.front(); q.pop();\n            used[nums[v]] = true;\n            for(int &u : ady[v]) q.push(u);\n        }\n    }\n};\n```
[]