2003. Smallest Missing Genetic Value in Each Subtree

There is a family tree rooted at 0 consisting of n nodes numbered 0 to n - 1. You are given a 0-indexed integer array parents, where parents[i] is the parent for node i. Since node 0 is the root, parents[0] == -1.

There are 105 genetic values, each represented by an integer in the inclusive range [1, 105]. You are given a 0-indexed integer array nums, where nums[i] is a distinct genetic value for node i.

Return an array ans of length n where ans[i] is the smallest genetic value that is missing from the subtree rooted at node i.

The subtree rooted at a node x contains node x and all of its descendant nodes.

class Solution {
    vector<vector<int>> adj;
    vector<int> res;
    vector<bool> vis;

    void dfs(int u, vector<int>& A) {
        if(vis[A[u]]) return;

        for(auto& v : adj[u])
            dfs(v, A);
        
        vis[A[u]] = true;
    }
public:
    vector<int> smallestMissingValueSubtree(vector<int> &parents, vector<int> &nums) {
        int u = find(begin(nums), end(nums), 1) - begin(nums), n = parents.size();
        adj = vector<vector<int>>(n);
        res = vector<int>(n, 1);
        vis = vector<bool>(n + 2, false);
        if(u == n) return res;

        for (int i = 0; i < n; i++) {
            if (parents[i] != -1) adj[parents[i]].push_back(i);
        }

        int miss = 1;
        while(u != -1) {
            dfs(u, nums);
            while(vis[miss]) miss++;
            res[u] = miss;
            u = parents[u];
        }

        return res;
    }
};