Easy To Understand || Three Approaches || O(n), O(a(n)*n), O(nlogn) || Proof & Code
Approach 1\n1. Requirement\n\t \tFind Mex (Minimum Excluded) of all sub-trees.\n2. Observation\n\t \tAll the nodes, except the one, which lies on the path from 
# **Approach 1**\n1. **Requirement**\n\t* \tFind Mex (Minimum Excluded) of all sub-trees.\n2. **Observation**\n\t* \tAll the nodes, except the one, which lies on the path from root to the node which contains the value = 1, will have the answer 1\n\t* \tProof:\n\t\t* \tLet say Node X has the value 1, Let P be the path from root to X\n\t\t* \tThen, any node Y on P, will have value 1 in its subtree, hence, ans[Y] > 1\n\t\t* \tLet, Z denotes nodes which are not on the path P, then it is clear that subtree(Z) can\'t contain 1, thus 1 is clearly MeX of the subtree(Z).\n\n3. **Algorithm**\n\t3.1. Find the path P, and store it in a vector path.\n\t3.2. For nodes which are not in the path, set their answer to the 1\n\t3.3. Now for nodes on Path P, we first consider the lowest node. We mark all values present in its subtree. Then, in the marked array we look for the smallest unmarked value.\n\n4. **Code Explanation**\n\t1. (3.1 & 3.2) is done with simple DFS traversal. Easy to understand.\n\t2. Then, we traverse the vector path, and maintain MeX (in variable j), starting from lowest node in the path, we mark all nodes in subtree, using dfs1() in code. \n\t3. Note: Traversing from lowest node to root in path, helps in making complexity O(n), because the MeX will be non decreasing in this order.\n\n5. **Complexities**\n\t* TC, SC: O(n)\n\n```\nvector<int> path;\nvector<int> ans;\nvector<int> mark;\n\nbool dfs(int s, int p, vector<vector<int>> &adj, vector<int>&nums){\n    bool flag = 0;\n    if(nums[s]==1){ flag = 1;}\n    for(auto &v : adj[s]){\n        if(v!=p){\n            if(dfs(v,s,adj,nums))\n                flag = 1;\n            else \n                ans[v] = 1;\n        }\n    }\n    if(flag) path.push_back(s);\n    return flag;\n\n}\n\nvoid dfs1(int s, int p, vector<vector<int>> &adj, vector<int>&nums){\n\n    mark[nums[s]] = 1;\n    for(auto &v : adj[s]){\n        if(v!=p && !mark[nums[v]]){\n            dfs1(v,s,adj,nums);\n        }\n    }\n}\n\nclass Solution {\npublic:\n    \n    vector<vector<int>> adj;\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size();\n        adj.resize(n+1);\n        for(int i=1; i<n; ++i)\n            adj[parents[i]].push_back(i);\n\n        ans.clear(); ans.resize(n);\n        path.clear();\n        mark.clear(); mark.resize(100005);\n        \n        if(!dfs(0,-1,adj,nums))\n            ans[0] = 1;\n        int j=1;\n        \n        for(auto &v : path){\n            dfs1(v,parents[v],adj,nums);\n            while(j<=n && mark[j]){j++;}\n            ans[v] = j;\n        }\n        return ans;\n        \n        \n    }\n};\n\n```\n\n# **Approach 2**\n- Pointer 4.3) gives us another hint to solve the problem, that is ans[parent] >= ans[child]\n- We find MeX of children.\n\t- ans[Parent] >= maxMex. where maxMex = max( Mex Of Children).\n\t- At each node, we add them to the set of their children. \n\t\t- Code: Union of two nodes in the dfs call.\n\t- Then, for parent we check first number >= maxMex, which is not present in the set of current node.\n\t\t- Code: I did this using while loop in the dfs function.\n\n- TC: O(a(n).n), where a(n) is ackermen constant, SC: O(n).\n```\nint n;\nvector<int> ans;\nint find(vector<int> &ds, int i) {\n    return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]);\n}\n\nbool Union(vector<int> &ds, int i, int j){\n\t i = find(ds, i), j = find(ds, j);\n\t if(i==j) return false;\n\t if(abs(ds[i]) < abs(ds[j])) swap(i,j); \n\t ds[i]+=ds[j]; \n\t ds[j]=i;\n\t return true;\n}\n\nint dfs(int s, int p, vector<vector<int>>&adj, vector<int>&nums, vector<int>&ds){\n    \n    int maxMex = 1;\n    if(nums[s]>=n+1) \n        nums[s] = n+1;\n    for(auto &v : adj[s]){\n        if(v!=p){\n            maxMex = max(maxMex, dfs(v,s,adj,nums,ds));\n            Union(ds,nums[s],nums[v]);\n        }\n    }\n    \n    while(maxMex<=n && find(ds,maxMex) == find(ds,nums[s])) maxMex++;\n    return ans[s] = maxMex;\n}\nclass Solution {\npublic:\n    \n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        n = parents.size();\n        vector<int> ds(n+2,-1);\n        vector<vector<int>> adj(n+1);\n        \n        for(int i=1; i<n; ++i)\n            adj[parents[i]].push_back(i);\n\n        ans.clear(); ans.resize(n);        \n        dfs(0,-1,adj,nums,ds);\n        return ans;\n    }\n};\n\n```\n# **Approach 3**\nI have just an idea, on how to solve this way, via using standard technique to solve for subtree queries.\n\n1. Store the DFS tour of the tree, in an array say arr.\n2. Now each subtree is a continous subarray arr.\n3. Then, use Range Query Data Structure on array arr, to find MeX in required ranges. \n\nTC should be around O(nlogn).\n\nAny further suggestions on this are welcomed.\n\n****Thank You. Please Write Your Constructive Feedbacks.***
[]