Trie 2

· · 题解

trie 树上二分与按位贪心

前置芝士 Trie 1。

CF1055F Tree and XOR

树上路径的异或和显然可以套路转化。记 S [i] 为第 i 个节点到根的路径异或和。则点 A 到点 B 路径的异或和就等于 S[A] \oplus S[B]。（因为 lca 上面的都消掉了）。那么原题就转化为给出 n 个数，求两两异或和的第 k 大。

这题根本不用建树，由于第一个编号比第二个小。直接如下：

for (int i = 2; i <= n; i++){
    int fa,w;
    cin >> fa >> w;
    a[i] = a[fa]^w; 
}

我们很轻松能想到一个做法，先将所有数放进 trie 里，预处理出每个节点有多少个数经过。二分最终答案，再扫一遍 trie 累加有多少数小于它，即为 cnt，比较 cnt 和 k，即可判断二分区间。

这样的复杂度是 nlog^2n 的，多出来一个 log 无法通过本题，考虑直接贪心枚举从高到低的每一位，查看当前这一位选 1 还是选 0 各有多少种对，记选 0 的有 cnt 对，将 cnt 和 k 比较决定选 0 还是选 1，如果选 1 的话 k=k-cnt，因为它是这一位选 1 条件下的第 k-cnt 小。

具体实现的话可以每个数都维护一个指针，即目前跳到了 trie 的哪个节点。累加 cnt 的时候就暴力扫一遍所有的数，看看接下来能不能走使这个数这一位异或和为零的儿子就可以了。

int ans = 0;
for (int i = 1; i <= n; i++) p[i] = 1;
for (int i = 62; i >= 0; i--){
    int cnt = 0;
    //此位取零的方案数 
    for (int j = 1; j <= n; j++){//暴力扫一遍每一个数
        int c = a[j]>>i&1; // 当前这位是什么 
        cnt += sz[trie[p[j]][c]];//sz 在建 trie 的时候维护即可
    }
    int pan = (K > cnt);//取零还是取一
    if (pan){//取一
        K -= cnt;
        ans += (1ll<<i);
    } 
    for (int j = 1; j <= n; j++){
        int c = a[j]>>i&1;
        p[j] = trie[p[j]][c^pan]; //每个数匹配到哪了
    }
}

比较坑的是，这题竟然卡内存。只能滚存一下字典树，比较容易绕晕。滚存其实只要在上面的代码上每层清空重来就行，维护 sz 再开一个数组记录原始每个数的当前层就行。

for (int i = 61; i >= 0; i--){
//此位取零的方案数 
for (int j = 1; j <= tot; j++){
    sz[j] = trie[j][0] = trie[j][1] = 0;
}
tot = cnt = 0;
for (int j = 1; j <= n; j++){
    int c = (a[j]>>i&1); // 当前这位是什么 
    if (!trie[old[j]][c]){
        tot++;
        old[j] = trie[old[j]][c] = tot;
    }
    else old[j] = trie[old[j]][c];
    sz[old[j]]++;
}
for (int j = 1; j <= n; j++){
    int c = (a[j]>>i&1);
    cnt += sz[trie[p[j]][c]];
} 
int pan = (K > cnt); // 取零还是取一
if (pan){
    K -= cnt;
    ans += (1ll<<i);
} 
for (int j = 1; j <= n; j++){
    int c = (a[j]>>i&1);
    p[j] = trie[p[j]][c^pan];
}

这道题还是 Trie 3 这里面问题的前置。