C++ Beats 70% Simple O(n) solution
\n# Approach\nWe only care about the tree with 1 in it, everything else will have 1 as the missing value - so we can initialise our answer array to full of 1s. 
\n# Approach\nWe only care about the tree with 1 in it, everything else will have 1 as the missing value - so we can initialise our answer array to full of 1s. We start our dfs from 1, everything under it will be marked as visited. We will maintain a variable \'lo\' which is the lowest integer that hasn\'t been visited yet. After the DFS from 1, we will just move up the parent chain until the root. Every single time, we will run a dfs to update the \'visited\' array for the subtree we are at. Then, we will increment the lo variable until the correct one is met. Note that lo will only increment at most 1e5 times, and the dfs will only dfs at most 1e5 times, so it is strictly O(n).\n# Intuition\nAt first, I was thinking we had to somehow maintain all the visited values for every node whilst dfsing, since if we are at the value 3, how do we know that 1 and 2 have been visited if they are in different subtrees? If we dfs from every node it will be O(n^2). Also can\'t really maintain a set of all visited nodes, because even if we do, how can we find the lo? The key is, if we have already dfsed, we want to do it in an order where we can maintain this visited array without having to redo it every iteration - basically with these types of questions, we are always trying to iterate on our current state in a certain order so that we can re-use already-computed information. In this case, the order is just up the tree, starting from node 1, since this is the only branch that matters. Also make sure you consider going up the tree, I was stuck on solutions that only go down! :)\n\n# Code\n```\nclass Solution {\npublic:\n    int n;\n    vector<int> adj[100001];\n    vector<int> nums, par;\n    int vis[100002];\n\n    void dfs(int u) {\n        vis[nums[u]] = 1;\n        for (int v : adj[u]) {\n            if (!vis[nums[v]]) dfs(v);\n        }\n    }\n\n    vector<int> smallestMissingValueSubtree(vector<int>& _par, vector<int>& _nums) {\n        nums = std::move(_nums);\n        par = std::move(_par);\n        n = nums.size();\n        vector<int> ans(n, 1);\n\n        for (int i = 0; i < n; i++) {\n            if (par[i] != -1)\n                adj[par[i]].push_back(i);\n        }\n        int u = 0;\n        for (int i = 0; i < n; i++) {\n            if (nums[i] == 1) {\n                u = i; break;\n            }\n        }\n        int lo = 1;\n        while (u != -1) {\n            dfs(u);\n            while (vis[lo]) lo++;\n            ans[u] = lo;\n            u = par[u];\n        }\n        return ans;\n    }\n};\n\n/*\n\n*/\n```
['C++']