Description

Submission

class Solution {
    typedef pair<int, int> PII;
    struct TrieNode {
        TrieNode* next[2];
        int count;
        TrieNode() {
            count = 0;
            for(int i = 0; i < 2; ++i) {
                next[i] = nullptr;
            }
        }
    };
    unordered_map<int, vector<PII>> node2quries; // node -> {val, idx}
    vector<vector<int>> children;
    vector<int> rets;
    TrieNode* root;
    

    void dfs(int cur) {
        TrieNode* node = root;
        for(int i = 31; i >= 0; --i) {
            int d = (cur>>i)&1;
            if(!node->next[d]) {
                node->next[d] = new TrieNode();
            }
            node = node->next[d];
            ++node->count;
        }

        for(auto [val, idx]: node2quries[cur]) {
            int ans = 0;
            node = root;
            for(int i = 31; i >= 0; --i) {
                int d = (val>>i)&1;
                if(node->next[1-d] && node->next[1-d]->count) {
                    ans = (ans << 1) + 1 - d;
                    node = node->next[1-d];
                } else {
                    ans = (ans << 1) + d;
                    node = node->next[d];
                }
            }
            rets[idx] = ans ^ val;
        }

        for(auto child: children[cur]) {
            dfs(child);
        }

        node = root;
        for(int i = 31; i >= 0; --i) {
            node = node->next[(cur>>i)&1];
            --node->count;
        }
    }
public:
    vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) {
        for(int i = 0; i < queries.size(); ++i) {
            node2quries[queries[i][0]].push_back({queries[i][1], i});
        }
        int n =parents.size();
        children.resize(n);
        rets.resize(queries.size());
        root = new TrieNode();
        int rootVal = -1;
        
        for(int i = 0; i < n; ++i) {
            if(parents[i] == -1) {
                rootVal = i;
                continue;
            }
            children[parents[i]].push_back(i);
        }
        dfs(rootVal);
        return rets;
    }
};