0x16 Trie
以下两题使用此模板。
最大异或对
考虑到我们用 01 Trie 维护一个字典树，然后尽可能选择与当前位相反的数位。从前往后遍历插入查询即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
| signed main() {
int n;
cin >> n;
int ans = 0;
XorTrie xt(n);
while (n--) {
int x;
cin >> x;
xt.insert(x);
ans = max(xt.query(x), ans);
}
cout << ans << "\n";
}
|
最长异或路径
注意到 $(a \oplus b) \oplus (a \oplus c)=b \oplus c$，因此对于每一个节点到根节点的前缀异或和，任意两个节点之间的路径异或和会等于这两个节点到根节点的异或和的异或和。因此参考上面的思路枚举每一个节点前缀异或和最大异或对即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| signed main() {
int n;
cin >> n;
vector adj(n + 1, vector<pair<int, int>>{});
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
vector<int> pre(n + 1);
vector<int> fa(n + 1);
queue<int> q;
q.push(1);
while (not q.empty()) {
int u = q.front(); q.pop();
for (auto &[v, w] : adj[u]) {
if (v == fa[u])
continue;
fa[v] = u;
pre[v] = pre[u] ^ w;
q.push(v);
}
}
XorTrie xt(n);
int ans = 0;
for (int i = 1; i <= n; i++) {
xt.insert(pre[i]);
ans = max(ans, xt.query(pre[i]));
}
cout << ans << "\n";
}
|