C++ 232ms 99.7%
Use a union-find structure par_on_chain to record every node\'s ancestor on the chain of 1->root. Deal with 1 first, then the remaining nodes are all on the cha
Use a union-find structure `par_on_chain` to record every node\'s ancestor on the chain of 1->root. Deal with 1 first, then the remaining nodes are all on the chain.\n\n```\nclass Solution {\npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size();\n        vector<int> n2i(100002, -1);\n        for (int i = 0; i < n; ++i)\n            n2i[nums[i]] = i;\n        if (n2i[1] == -1)\n            return vector<int>(n, 1);\n        \n        unordered_set<int> chain;\n        for (int i = n2i[1]; i != -1; i = parents[i]) {\n            chain.insert(i);\n        }\n        vector<int> par_on_chain(n, -1);\n        function<int(int)> get_chain = [&](int cur) {\n            if (cur == -1)\n                return -1;\n            if (par_on_chain[cur] != -1)\n                return par_on_chain[cur];\n            if (chain.count(cur))\n                return cur;\n            return par_on_chain[cur] = get_chain(parents[cur]);\n        };\n        \n        vector<int> res(n, -1);\n        for (int i = 0; i < n; ++i) {\n            par_on_chain[i] = get_chain(i);\n            if (!chain.count(i))\n                res[i] = 1;\n        }\n        \n        vector<int> child(n, -1);\n        for (int node : chain) {\n            if (parents[node] == -1)\n                continue;\n            child[parents[node]] = node;\n        }\n        int k = 2;\n        for (;; ++k) {\n            if (n2i[k] == -1)\n                break;\n            int cur = n2i[k];\n            int par = par_on_chain[cur];\n            int node = child[par];\n            child[par] = -1;\n            while (node != -1 && res[node] == -1) {\n                res[node] = k;\n                node = child[node];\n            }\n        }\n        for (int i = 0; i < n; ++i)\n            if (res[i] == -1)\n                res[i] = k;\n        return res;\n    }\n};\n```
[]