最大异或结点 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 100000 + 100;
const int maxcnt = 3200000 + 100;
const int Size = 2;

struct Trie {
    int root, cnt;
    int tree[maxcnt][Size];
    int val[maxcnt];

    int create() {
        ++cnt;
        memset(tree[cnt], 0, sizeof(tree[cnt]));
        val[cnt] = 0;
        return cnt;
    }

    void Init() {
        cnt = 0;
        root = create();
    }

    inline int id(int x, int dig) {
        return (x >> dig) & 1;
    }

    void add(int x, int d) {
        int pos = root;
        for(int i = 30; i >= 0; --i) {
            int w = id(x, i);
            if(tree[pos][w] == 0) {
                tree[pos][w] = create();
            }
            pos = tree[pos][w];
            val[pos] += d;
        }
    }

    int query(int x) {
        int pos = root;
        int ret = 0;
        for(int i = 30; i >= 0; --i) {
            int w = id(x, i);
            if (tree[pos][w ^ 1] != 0 && val[tree[pos][w ^ 1]] != 0) {
                ret |= (1 << i);
                pos = tree[pos][w ^ 1];
            } else {
                pos = tree[pos][w];
            }
        }
        return ret;
    }
};

int n, fa, ans;
int num[maxn];
vector<int> G[maxn];
Trie trie;

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    cin >> n;
    trie.Init();
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        trie.add(num[i], 1);
    }
    for (int i = 0; i < n; ++i) {
        cin >> fa;
        if (fa != -1) {
            G[fa].push_back(i);
            G[i].push_back(fa);
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int pos : G[i]) {
            trie.add(num[pos], -1);
        }
        ans = max(ans, trie.query(num[i]));
        for (int pos : G[i]) {
            trie.add(num[pos], 1);
        }
    }
    cout << ans << endl;

    return 0;
}