My notes
A O(nlogn) solution with dsu(\u542F\u53D1\u5F0F\u5408\u5E76)\u3002\n\nThe idea is to maintain a set of values for each node and find the first missing. \n\nKey 
A O(nlogn) solution with dsu(\u542F\u53D1\u5F0F\u5408\u5E76)\u3002\n\nThe idea is to maintain a set of values for each node and find the first missing. \n\nKey points:\n1 When merging sets of children, move values from smaller sets to bigger sets. This is to make sure the O(nlogn) time complexity. \n2 The missing value of parent is at least as big as all children.\n3 We only need to allocate new sets for leaves, this way we can avoid copying the biggest set bottom up. The solution below has this improvement, and without will also AC.\n\n```\nclass Solution {\npublic:\n    int n;\n    vector<vector<int>> adjList;\n    vector<int> nums;\n    vector<int> ans;\n    \n    vector<int> nodeToSet;  // mapping of tree node to index of sets values\n    vector<unordered_set<int>> values; // sets of values, linked list style \n    int idx = 0; // allocate new sets, first set start with 1\n    \n    void dfs(int u) {\n\t    // leaf node, allocate new set and return\n        if (adjList[u].size() == 0) {\n            nodeToSet[u] = ++idx;\n            values[nodeToSet[u]].insert(nums[u]);\n            if (nums[u] == 1)\n                ans[u] = 2;\n            \n            return;\n        }\n        \n        for (int v : adjList[u]) {\n\t\t    // typical post order, complete one child and merge\n            dfs(v);\n            \n\t\t\t// parent is not allocated, this means just complete the first child, point parent to first child\'s set\n            if (nodeToSet[u] == 0)\n                nodeToSet[u] = nodeToSet[v]; \n            else {\n\t\t\t    // key point 1: make sure nodeToSet[u] parent is the bigger set\n                if (values[nodeToSet[u]].size() < values[nodeToSet[v]].size())\n                    swap(nodeToSet[u], nodeToSet[v]);\n                \n\t\t\t\t// move all values from smaller set child to bigger parent\n                for (int n : values[nodeToSet[v]]) {\n                    values[nodeToSet[u]].insert(n);\n                }\n            }\n\t\t\t\n            // key point 2: missing value of parent is as big as all children\n            ans[u] = max(ans[u], ans[v]);\n        }\n        \n\t\t// don\'t forget to insert parent\'s value\n        values[nodeToSet[u]].insert(nums[u]);\n\t\t\n\t\t// I am a little bit nervous here, will this lead to n^2??\n        while (values[nodeToSet[u]].count(ans[u])) {\n            ans[u]++;\n        }\n    }\n    \n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& _nums) {\n        n = parents.size();\n        nums = _nums;\n        adjList.resize(n);\n        \n        for (int i = 1; i < n; i++) {\n            adjList[parents[i]].push_back(i);\n        }\n        \n        ans = vector<int>(n, 1);\n        nodeToSet.resize(n);\n        values.resize(n);\n        \n        dfs(0);\n        \n        return ans;\n    }\n};\n```
[]