(01字典树)

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N;

struct relations {
    int num;
    vector<int> children;
    int parent = -1;
};

struct TrieNode {
    TrieNode *left;
    TrieNode *right;
    int count;

    TrieNode() {
        left = nullptr;
        right = nullptr;
        count = 0;
    }
};

class Trie {
private:
    TrieNode *root;

public:
    Trie() {
        root = new TrieNode;
    }

    void insert(int num) {
        TrieNode *node = root;
        for (int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (bit == 0) {
                if (!node->left) {
                    node->left = new TrieNode;
                }
                node = node->left;
            } else {
                if (!node->right) {
                    node->right = new TrieNode;
                }
                node = node->right;
            }
            node->count++;
        }
    }

    void remove(int num) {
        TrieNode *node = root;
        for (int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (bit == 0) {
                TrieNode *child = node->left;
                child->count--;
                node = child;
            } else {
                TrieNode *child = node->right;
                child->count--;
                node = child;
            }
        }
    }

    int find_max_XOR(int num) {
        int _xor = 0;
        TrieNode *node = root;

        for (int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            int opposite = 1 - bit;

            if (opposite == 0) {
                if (node->left && node->left->count != 0) {
                    _xor = (_xor << 1) | 1;
                    node = node->left;
                } else {
                    _xor = (_xor << 1);
                    node = node->right;
                }
            } else {
                if (node->right && node->right->count != 0) {
                    _xor = (_xor << 1) | 1;
                    node = node->right;
                } else {
                    _xor = (_xor << 1);
                    node = node->left;
                }
            }
        }

        return _xor;
    }
};

int main() {
    cin >> N;
    Trie T;
    vector<relations> serial(N);
    for (int i = 0; i < N; ++i) {
        int number;
        cin >> number;
        T.insert(number);
        serial[i].num = number;
    }
    for (int i = 0; i < N; ++i) {
        int p;
        cin >> p;
        serial[i].parent = p;
        if (p != -1) {
            serial[p].children.push_back(i);
        }
    }

    int max_xor = -1;
    for (int i = 0; i < N; ++i) {
        if (serial[i].parent != -1) {
            T.remove(serial[serial[i].parent].num);
        }
        vector<int> children = serial[i].children;
        for (auto child: children) {
            T.remove(serial[child].num);
        }

        max_xor = max(max_xor, T.find_max_XOR(serial[i].num));

        if (serial[i].parent != -1) {
            T.insert(serial[serial[i].parent].num);
        }
        for (auto child: children) {
            T.insert(serial[child].num);
        }
    }

    cout << max_xor;
    return 0;
}