[C++, O(n)] Case Work DFS ¯\_(ツ)_/¯
\nclass Solution {\n    vector<vector<int>>adj;\n    int n;\n    vector<int>a;\n    vector<int>ans;\n    vector<int>subMin;\n    void dfs(int i, int cur){\n    
```\nclass Solution {\n    vector<vector<int>>adj;\n    int n;\n    vector<int>a;\n    vector<int>ans;\n    vector<int>subMin;\n    void dfs(int i, int cur){\n        ans[i] = cur;\n        if(adj[i].empty())return;\n        if(cur<subMin[i]){\n            for(auto &x:adj[i])\n                dfs(x, cur);\n            return;\n        }\n        vector<pair<int,int>>aj;\n        for(auto &x:adj[i])\n            aj.push_back({subMin[x], x});\n\n        int mn = INT_MAX, mni=-1;\n        for(auto &[x,y]:aj){\n            if(x<mn){\n                mn=min(mn, x);\n                mni=y;\n            }\n        }\n        \n        if(a[i]<mn){\n            for(auto &x:adj[i]){\n                dfs(x, a[i]);\n            }\n            return;\n        }\n        \n        for(int i=0; i<aj.size(); i++){\n            if(aj[i].second!=mni)\n                dfs(aj[i].second, min(cur, mn));\n        }\n        int smn = min(a[i], cur);\n        for(int i=0; i<aj.size(); i++){\n            if(aj[i].second!=mni)\n                smn=min(smn, aj[i].first);\n        }\n        dfs(mni, smn);\n    }\n    \n    int dfs2(int i){\n        int ans=a[i];\n        for(auto &x:adj[i])\n            ans=min(ans, dfs2(x));\n        return subMin[i] = ans;\n    }\n    \npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& par, vector<int>& nums) {\n        n=par.size();\n        adj.resize(n);\n        ans.resize(n);\n        subMin.resize(n);\n        for(int i=1; i<n; i++)\n            adj[par[i]].push_back(i);\n        a=nums;\n        dfs2(0);\n        unordered_set<int>vals;\n        for(auto &x:a)vals.insert(x);\n        int i=1;\n        while(i<=n+1){\n            if(vals.find(i)==vals.end())break;\n            i++;\n        }\n        dfs(0, i);\n        return ans;\n    }\n};\n```
['Depth-First Search']