Simple merging of intervals of numbers covered by children for each node
For each node, we try to get the intervals of numbers covered by itself and its children, and get the min uncovered number from the first interval.  For any nod
For each node, we try to get the intervals of numbers covered by itself and its children, and get the min uncovered number from the first interval.  For any node, simple merge can get its sorted disjoint interval list from those of its chidlren.\n\n```\nclass Solution {\npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        auto n = parents.size();\n        std::vector<std::vector<int>> tree(n);\n        for (size_t i = 0; i < n; ++i) {\n            if (parents[i] < 0) continue;\n            tree[parents[i]].push_back(i);\n        }\n        \n        std::vector<int> results(n);\n        std::vector<Intervs> intervs(n);\n        \n        solve(tree, nums, results, intervs, 0);\n        \n        return results;\n    }\n    \nprivate:\n    using Interv = std::pair<int, int>;\n    using Intervs = std::vector<Interv>;\n\n    void solve(\n        const std::vector<std::vector<int>>& tree, const std::vector<int>& nums,\n        std::vector<int>& results, std::vector<Intervs>& intervs,\n        size_t node\n    ) {\n        const auto& children = tree[node];\n        int& result = results[node];\n        Intervs& interv = intervs[node];\n        \n        // Intervals to merge.\n        std::vector<std::pair<Intervs::const_iterator, Intervs::const_iterator>> child_intervs{};\n        child_intervs.reserve(children.size() + 1);\n        Intervs node_intervs = {{nums[node], nums[node]}};\n        child_intervs.push_back({node_intervs.cbegin(), node_intervs.cend()});\n        for (auto i : children) {\n            solve(tree, nums, results, intervs, i);\n            child_intervs.push_back({intervs[i].cbegin(), intervs[i].cend()});\n        }\n            \n        while (!child_intervs.empty()) {\n            auto it = std::min_element(child_intervs.begin(), child_intervs.end(), [](const auto& i, const auto& j) {\n                return i.first->first < j.first->first;\n            });\n\n            const auto& curr = *it->first;\n            if (interv.empty() || interv.back().second + 1 < curr.first) {\n                interv.push_back(curr);\n            } else {\n                interv.back().second = std::max(interv.back().second, curr.second);\n            }\n            ++it->first;\n            if (it->first == it->second) {\n                child_intervs.erase(it);\n            }\n        }\n        \n        if (interv.front().first != 1) {\n            result = 1;\n        } else {\n            result = interv.front().second + 1;\n        }\n    }\n};\n```
[]