trie（字典树）学习笔记
trie 可以在 \(O(nL)\) 的时间， \(O(n\left| \Sigma\right|L)\) 的空间完成插入，查找字符串。其中 \(L\) 为字符串长，\(\Sigma\) 为字符集
int trie[N][26], tot;
int tag[N];
void insert() {
int n = str.size();
int u = 0;
for (int i = 0; i < n; i++) {
int x = str[i] - 'a';
if (!trie[u][x]) trie[u][x] = ++tot;
u = trie[u][x];
}
tag[u] = 1;
}
void query() {
int n = str.size();
int u = 0;
for (int i = 0; i < n; i++) {
int x = str[i] - 'a';
if (!trie[u][x]) {
break;
}
u = trie[u][x];
}
if (tag[u] == 0) {
cout << "WRONG\n";
}
else if (tag[u] == 1) {
cout << "OK\n";
tag[u] = 2;
}
else {
cout << "REPEAT\n";
}
}
trie 维护异或极值
问题：最长异或路径
给定一棵 \(n\) 个点的无向带权树，结点下标从 \(1\) 开始到 \(n\)。寻找树中找两个结点，求最长的异或路径。边权 \(w\) 有
\(w < 2^{31}\)
解析：记 \(d(u, v)\) 为 \(u\to v\) 的异或路径值。
我们选择一个点为根，不妨为 \(1\) 。
那么我们有这个重要结论： \(d(1,u) \oplus d(1, v)=d(u,v)\) 这是由于 \(a\oplus a=0\) 和 \(a\oplus 0=a\)， \(u, v\) 的 lca 部分被抵消了。
那么问题就转化成了 枚举每个 \(d(1, u)\) 找到其对应的 \(d(1, v)\) 使得 \(d(1,u) \oplus d(1, v)\) 最大，更新答案。
如何快速做到这一点呢？我们可以注意到一个性质：对每个数补全到 \(31\) 位后，如果 \(u\) 与 \(v\) 的最高位不同，但 \(u\) 与 \(w\) 的最高位相同，那么 \(u\oplus v\) 一定大于 \(u\oplus w\)。
基于这一点，我们可以将每个 \(d(1, u)\) 都将其视作一个 \(31\) 位的二进制数插入到 trie 中。枚举 \(d(1, u)\) 时从最高位开始采用贪心，尽可能地向不同于当前这一位的子树走，最后的结果就是最大的。
时空复杂度同上。这里 \(\Sigma\) 为 \(2\)，\(L\) 为 \(31\)。
代码：
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
const int N = 1e5 + 10, M = 31;
int trie[N * M][2], tot;
int dis[N];
int n, ans;
vector<pii> g[N];
void insert(int x) {
for (int i = 30, u = 0; i >= 0; i--) {
int c = (x >> i) & 1; // i-th bit
if (!trie[u][c]) trie[u][c] = ++tot;
u = trie[u][c];
}
}
void update(int x) {
int res = 0;
for (int i = 30, u = 0; i >= 0; i--) {
int c = (x >> i) & 1;
if (trie[u][!c]) {
u = trie[u][!c];
res += (1 << i);
}
else u = trie[u][c];
}
ans = max(ans, res);
}
void dfs(int u, int fa) {
insert(dis[u]);
update(dis[u]);
for (auto x : g[u]) {
int v = x.fi, w = x.se;
if (v == fa) continue;
dis[v] = dis[u] ^ w;
dfs(v, u);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
auto add = [&] (int u, int v, int w) {
g[u].push_back({v, w});
};
add(u, v, w);
add(v, u, w);
}
dfs(1, 0);
cout << ans << "\n";
return 0;
}