C++ Small-To-Large Merging in DFS
The idea is to do a DFS. For each node, I calculate these two informations:\n- All the values in the subtrees. I use set for this.\n- The smallest-missing-value
The idea is to do a DFS. For each node, I calculate these two informations:\n- All the values in the subtrees. I use set for this.\n- The smallest-missing-value for that node.\n\nHowever, naive approach may lead to an O(N^2) complexity.\n\nTo address this, I use small-to-large merging idea. This is done by reusing the largest set stored by the childrens, and that children\'s smallest-missing-value. Then, only the smaller sets needs to be iterated to be merged to this reused set.\n\nAfter all values for that subtree already collected, then increment the smallest-missing-value one by one by checking whether it exists in the "new" set or not.\n\nThe complexity of the reusing-and-merging part should be O(N lg^2 N) (algo-wise, should be O(N lg N), but the insertion to the set adds another O(lg N)). The complexity of incrementing smallest-missing-value should be the same.\n\n```\nclass Solution {\nprivate:\n    struct Node {\n        set<int> vals;\n        int curNotExist;\n        \n        Node(int val) {\n            vals.insert(val);\n            curNotExist = val == 1? 2 : 1;\n        }\n        \n        void print() {\n            printf("vals:\\n");\n            for (int u : vals) {\n                printf("%d ", u);\n            }\n            printf("\\n");\n            \n            printf("curNotExist: %d\\n", curNotExist);\n        }\n    };\n    \n    Node* traverse(int now, vector<vector<int>> &adjList, vector<int> &smallestMissingValue, vector<int> &nums) {\n        vector<Node*> values;\n        for (int u : adjList[now]) {\n            Node* val = traverse(u, adjList, smallestMissingValue, nums);\n            values.push_back(val);\n        }\n        \n        if (values.size() == 0) {\n            Node* nowVal = new Node(nums[now]);\n            smallestMissingValue[now] = nowVal->curNotExist;\n            \n            return nowVal;\n        }\n        \n        int greatestId = 0;\n        int greatestSize = values[greatestId]->vals.size();\n        for (int i = 1, sz = values.size(); i < sz; i++) {\n            if (values[i]->vals.size() > greatestSize) {\n                greatestId = i;\n                greatestSize = values[i]->vals.size();\n            }\n        }\n        \n        Node* &valAns = values[greatestId];\n        valAns->vals.insert(nums[now]);\n        for (int i = 0, sz = values.size(); i < sz; i++) {\n            if (i == greatestId) {\n                continue;\n            }\n            \n            for (int u : values[i]->vals) {\n                valAns->vals.insert(u);\n            }\n        }\n        \n        // valAns->print();\n        \n        auto ptrValNow = valAns->vals.find(valAns->curNotExist);\n        if (ptrValNow == valAns->vals.end()) {\n            smallestMissingValue[now] = valAns->curNotExist;\n            return valAns;\n        }\n        \n        while (ptrValNow != valAns->vals.end() && *ptrValNow == valAns->curNotExist) {\n            valAns->curNotExist++;\n            ptrValNow++;\n        }\n        \n        // valAns->print();\n        \n        smallestMissingValue[now] = valAns->curNotExist;\n        return valAns;\n    }\n    \npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int N = parents.size();\n        \n        vector<vector<int>> adjList(N, vector<int>());\n        for (int i = 1; i < N; i++) {\n            adjList[parents[i]].push_back(i);\n        }\n        \n        vector<int> smallestMissingValue(N, 0);\n        \n        traverse(0, adjList, smallestMissingValue, nums);\n        \n        return smallestMissingValue;\n    }\n};\n```
['Depth-First Search', 'C']