1938. Maximum Genetic Difference Query

https://leetcode.com/problems/maximum-genetic-difference-query/


struct TrieNode{
    TrieNode* children[2];
    int freq;
    TrieNode(){
        this->children[0]=nullptr;
        this->children[1]=nullptr;
        freq=0;
    }
};

class Solution {
private:
    vector<vector<int>> adj;
    TrieNode* root;
    vector<int> res;
    unordered_map<int,vector<int>> mpp;
public:
    void increment_decrement(int num, int decide){
        TrieNode* pCrawl=root;
        for(int i=31;i>=0;i--){
            int state=(num >> i) & 1;
            if(pCrawl->children[state]==nullptr){
                pCrawl->children[state]=new TrieNode();
            }
            pCrawl=pCrawl->children[state];
            pCrawl->freq+=decide;
        }
        pCrawl->freq+=decide;
    }

    int max_XOR(int num){
        int res=0;
        TrieNode* pCrawl=root;
        for(int i=31;i>=0;i--){
            int state=(num >> i) & 1;
            if(pCrawl->children[state ^ 1]!=nullptr && pCrawl->children[state ^ 1]->freq>0){
                pCrawl=pCrawl->children[state ^ 1];
                res=res | (1 << i);
            }
            else if(pCrawl->children[state]->freq>0){
                pCrawl=pCrawl->children[state];
            }
            else{
                return 0;
            }
        }
        return res;
    }

    void dfs(int node, vector<vector<int>> &queries){
        increment_decrement(node,1);
        if(mpp.find(node)!=mpp.end()){
            for(auto index: mpp[node]){
                int val=queries[index][1];
                int ans=max_XOR(val);
                res[index]=ans;
            }
            mpp.erase(node);
        }
        for(auto nei: adj[node]){
            dfs(nei,queries);
        }
        increment_decrement(node,-1);
    }

    vector<int> maxGeneticDifference(vector<int>& parent, vector<vector<int>>& queries){
        root=new TrieNode();
        int Q=queries.size();
        res.resize(Q);
        for(int i=0;i<Q;i++){
            mpp[queries[i][0]].push_back(i);
        }
        int root;
        adj.resize(parent.size());
        for(int i=0;i<parent.size();i++){
            if(parent[i]==-1){
                root=i;
                continue;
            }
            adj[parent[i]].push_back(i);
        }
        dfs(root,queries);
        return res;
    }
};