C++ With Explanation
Intuition\nThis case is pretty tricky, the concept is easy to understand:\nthe node1\'s childs/brothers/cousins/uncles return value should be 1\n\n1. we start f
# Intuition\nThis case is pretty tricky, the concept is easy to understand:\nthe node1\'s childs/brothers/cousins/uncles return value should be 1\n\n1. we start from node which value is 1 (ndoe1)\n2. we traverse all the substree from node1 and doing two things\n    * return value of each node in subtree should be 1\n    * add each node value in subtree to a "set"\n3. iterate from 1 to maxvalue to check missing value of node1\n \n4. we traverse to node1\'s parent\n5. we traverse all the substree except node1 and doing same things\n    * return value of each node in subtree should be 1\n    * add each node value in subtree to a "set"\n6. iterate from "return of node1" to maxvalue to check missing value of node1 (in this case, missing value is monotonic increasing)\n\n7. repeat step 4~6\n\nThe time complexity is O(n) because every node we only traverse once\n\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    \n    unordered_set<int> mySet;\n    void dfs(vector<vector<int>> &childs, vector<int>& nums, int node, vector<int>& vRet)\n    {\n        vRet[node] = 1;\n        mySet.insert(nums[node]);\n        for(int& child: childs[node])\n        {\n            dfs(childs, nums, child, vRet);\n        }\n    }\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size();\n        vector<vector<int>> childs(n);\n        int iMaxValue = *max_element(nums.begin(), nums.end());\n        //int iMaxValue = 100001;\n        int node1 = -1;\n        if(nums[0]==1) node1 = 0;\n        for(int i=1; i<n; i++)\n        {\n            childs[parents[i]].push_back(i);\n            if(nums[i] == 1) node1 = i;\n        }\n        if(node1 == -1) return vector<int>(n, 1);\n\n        vector<int>vRet(n);\n        int node = node1;\n        int iSmallMiss = 2;\n        while(node !=-1)\n        {\n            mySet.insert(nums[node]);\n            for(int& child:childs[node])\n            {\n                if(mySet.find(nums[child]) == mySet.end())\n                {\n                    dfs(childs, nums, child, vRet);\n                }\n            }\n\n            for(int i=iSmallMiss; i<=iMaxValue+1; i++)\n            {\n                if(mySet.find(i) == mySet.end())\n                {\n                    vRet[node] = i;\n                    iSmallMiss = i;\n                    break;\n                }\n            }\n            node = parents[node];\n\n        }\n        \n        return vRet;\n        \n        \n    }\n};\n```
['C++']