c++ persistent segment tree
Here is a solution using persistent segment tree\n1. we store the DFS time during post-order traversal in dfn[i]\n2. make a persistent seg tree that is indexed 
Here is a solution using persistent segment tree\n1. we store the DFS time during post-order traversal in `dfn[i]`\n2. make a persistent seg tree that is indexed by values and stores the _minimum_ `dfn` (i.e. `tree[L,R]` is the minimum DFS time for all values in the range `[L,R]`)\n\t- all values in the tree are initialized to `-1`\n3. for each DFS time `t`, update the segment tree; this makes a new version of the data structure\n\t- _important property:_ for each subtree root with time `t`, all DFS times in the tree of version `t` are <= `t`.\n4. query: to find the smallest missing value in subtree with starting time `left` and root time `t` in value range `[L, R]`\n\t- if `tree[L, mid] < left`, the missing value must in the left subtree, go to left\n\t- else go to right\n\t- stop when at leaf, return the leaf index\n\n``` cpp\nclass Solution {\n    struct node {\n        node() : val(-1) { sons[0] = sons[1] = 0; }\n        array<int,2> sons;\n        int val;\n    };\n    vector<node> ns;\n    vector<int> roots;\n    int N;\n    int nn() {\n        ns.emplace_back();\n        return ns.size()-1;\n    }\n    void init(int n) {\n        nn();\n        roots.push_back(0);\n        N = n;\n    }\n    void update(int idx, int val) {\n        function<void(int,int,int,int)> f = [&](int i, int p, int l, int r) {\n            if(l == r) {\n                ns[i].val = val; // no need to do min here, values are all unique\n                return;\n            }\n            ns[i].sons = ns[p].sons;\n            int m = l + ((r-l) >> 1);\n\n            if(idx <= m) {\n                ns[i].sons[0] = nn();\n                f(ns[i].sons[0], ns[p].sons[0], l, m);\n            } else {\n                ns[i].sons[1] = nn();\n                f(ns[i].sons[1], ns[p].sons[1], m+1, r);\n            }\n            ns[i].val = min(ns[ns[i].sons[0]].val, ns[ns[i].sons[1]].val);\n        };\n\n        int p = roots.back();\n        roots.push_back(nn());\n        f(roots.back(), p, 0, N-1);\n    }\n    int query(int version, int left) {\n        function<int(int,int,int)> f = [&](int i, int l, int r) {\n            if(l == r) {\n                return l;\n            }\n            int m = l +  ((r-l) >> 1);\n            int lval = ns[ns[i].sons[0]].val;\n            if(lval < left) {\n                return f(ns[i].sons[0], l, m);\n            } else {\n                return f(ns[i].sons[1], m+1, r);\n            }\n        };\n        return f(roots[version], 0, N-1);\n    }\n\npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size();\n        int m = *max_element(nums.begin(), nums.end()) + 1;\n\n        vector<vector<int>> adj(n);\n        vector<pair<int,int>> dfn(n);\n        vector<int> arr(n);\n        vector<int> ret(n);\n\n        init(m);\n        for(int i=1; i<n; ++i) {\n            adj[parents[i]].push_back(i);\n        }\n\n        int t = 0;\n        function<void(int,int)> f = [&](int i, int p) {\n            dfn[i].first = t;\n            for(int j : adj[i]) {\n                if(j != p)\n                    f(j,i);\n            }\n            arr[t++] = nums[i];\n            dfn[i].second = t;\n        };\n\n        f(0,-1);\n        for(int i=0; i<n; ++i) {\n            update(arr[i]-1, i);\n        }\n        for(int i=0; i<n; ++i) {\n            auto [l,r] = dfn[i];\n            ret[i] = query(r, l) + 1;\n        }\n        return ret;\n    }\n};\n```
['Tree', 'C']