01-Trie

‍

如果不理解 Trie 树的可以看我的之前的文章 Trie 树 – ztr 的小窝 (ztrztr.top)。

01 Trie 树，是运用 Trie 的思想储存一些数，从而实现省空间。

实现

01 Trie 树，是把原本是字符串中的都换成了一个数的二进制串。

对于添加数的操作，我们把数按二进制把二进制中的每一位拆分，然后按 Trie 的存储方式存。

比如说 $5 = (101)_2$，那么我们就把 $5$ 转换成字符串 101​，然后安装模板加入到 Trie 数。

而且，这样的一个 Trie 的深度最多为 $\log_2 \max\{a_i\}$，也就是要存的数中最大的数以 $2$ 为底的对数。

而且，这样的一个树每一个节点的子节点的数量最多是 $2$，也就是这个树是一个二叉树。

例题

P4551 最长异或路径 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

首先，我们需要理解一个异或的特性：当一个数异或一个数的结果再异或之前异或的那个数的结果就是最开始的数本身。

这样可能有点绕，那么我们用数学语言描述一下：

$$a \oplus x \oplus x = a$$

那么在这道题中，从 $x$ 到 $y$ 的异或路径就是从 $1$ 到 $x$ 的异或路径再异或从 $1$ 到 $y$ 的异或路径。

道理很显然。

所以这道题我们就按从 $1$ 到 $x$ 的异或路径来建 Trie 树，然后计算的时候按照以下贪心思想：

如果这个子树有两个子节点，那么就换一个子节点走下去，否则就按照这个子节点走下去。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n;
vector <int> e[100005], v[100005];
int s[100005];
int tr[1000005][30];
int cnt=  0;
void build (int val, int x) {
    for(int i = (1 << 30); i; i >>= 1){
        bool c=val&i;
        if(!tr[x][c]){
            tr[x][c]=++ cnt;
        }
        x = tr[x][c];
    }
}
void dfs1(int nw) {
    for (int i = 0; i < e[nw].size(); i ++) {
        int to = e[nw][i];
        s[to] = s[nw] ^ v[nw][i];
        dfs1(to);
    }
}
int dfs2(int val, int x) {
    int ans = 0;
    for(int i = (1 << 30); i; i >>= 1){
        bool c=val&i;
        if(tr[x][!c]){
            ans += i;
            x = tr[x][!c];
        } else x = tr[x][c];
      
    }
    return ans;
}
int maxn = -1e9;
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i ++) {
        int x, y, z; cin >> x >> y >> z;
        e[x].push_back(y);
        v[x].push_back(z);
    }
    dfs1(1);
    for (int i = 1; i <= n; i ++) {
        // cout << s[i] << "\n";
        build(s[i], 0);
    }
    for (int i= 1; i <= n; i ++) maxn = max(maxn, dfs2(s[i], 0));
    cout << maxn;
    return 0;
}