C++ | O(n)
Find the required path from node 0 (root node) to node with value 1. All the nodes not in this path has the minimum excluded value as 1. \nNow, you will only ne
Find the required path from node 0 (root node) to node with value 1. All the nodes not in this path has the minimum excluded value as 1. \nNow, you will only need to find mex (the minimum excluded value) for nodes in this path.\nYou will traverse the path from the node with value 1 and move towards 0 and also keep also keep the visited nodes for subtree at each of these nodes. \nThen you just check whether value m (mex till now) is in the subtree. While it is not in subtree rooted at u you just keep increasing m.\n\nCheck the code and invariant for better understanding.\n\n```c++\n#define N 100002\nclass Solution {\npublic:\n    void dfs(int u, vector<vector<int>>& adj_list, vector<bool>& subtree) {\n        if (subtree[u]) {\n            return;\n        }\n        subtree.at(u) = true;\n        for (int v: adj_list[u]) {\n            dfs(v, adj_list, subtree);\n        }\n    }\n    \n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size();\n        \n        // Finding adjacency list\n        vector<vector<int>> adj_list(n);\n        for (int i=0; i<n; i++) {\n            int u = parents[i];\n            if (u != -1) {\n                adj_list[u].push_back(i);\n            }\n        }\n        \n        // Gives index_with_val[v] = index of a node with value = v\n        vector<int> index_with_val = vector<int>(N, -1);\n        for (int i=0; i<n; i++) {\n            index_with_val[nums[i]] = i;\n        }\n        \n        vector<int> ans(n, 1);\n        int m = 1;\n        vector<bool> subtree(n, false);\n        // Move from node with value 1 towards node with value 0.\n        for (int u = index_with_val[1]; u != -1; u = parents.at(u)) {\n            dfs(u, adj_list, subtree);\n            // Invarient: subtree = subtree at node u\n            \n            // Find the node with value m and check if that node is in the subtree. While it is in the subtree you keep increasing m\n            int x = index_with_val[m];\n            while (x != -1 && subtree.at(x)) {\n                m += 1;\n                x = index_with_val[m];\n            }\n            \n            // m = Minimum value not present in the subtree rooted at u\n            ans[u] = m;\n        }\n        \n        return ans;\n    }\n};\n```
[]