把树上路径异或转为两个根前缀异或，再用 01-Trie 求最大异或对。
OJ: luogu
题目 ID: P4551
难度:普及+/提高
标签:01-Trie异或树python
日期: 2026-07-16 19:57
题意
求带权树上任意两点间路径边权异或和的最大值。
思路
先说人话：路径异或被"异或两次抵消"降维成前缀异或对，最大异或对又被"高位支配低位"降维成逐位贪心，01-Trie 只负责回答贪心每一步需要的"存在性"。
第一问：能枚举点对吗？
n ≤ 1e5，点对约 5×10⁹ 个，枚举直接超时。必须把"路径"整体变成一个好算的东西，而不是逐对去走。
第二问：路径异或能用前缀吗？
能——这是本题的第一把钥匙。树上路径问题通常绕不开 LCA，路径长度有公式 xor_from_root[u] 为根到 u 的边权异或，则任意路径 u→v 的异或为：
text
xor_path(u, v) = xor_from_root[u] ^ xor_from_root[v]因为 pre[u] 和 pre[v] 都包含"根→lca"这一段，异或两次恰好抵消（
第三问：n 个数两两配对不还是 O(n²) 吗？
所以要利用异或的贪心结构：两个数比大小先比最高位——第 k 位的 1 贡献
第四问：每一位的"存在性"怎么快速查？
用 01-Trie。普通 Trie 用来存单词，01-Trie 存数字的二进制表示：本题边权
第五问：为什么要"边插边查"，而且先插 0？
每个点对只需被检查一次：扫描到第 j 个值时，Trie 里只有"之前出现过的值"，查询完再插入自己——点对 (i, j) 恰好在这一步被检查一次，不重不漏。必须先插入 0（根的前缀异或），否则"单点路径"（u 到根的路径 = pre[u] ^ 0）会被漏掉。
Python 知识
- 显式栈遍历树，避免递归深度限制。
- 算出根异或后
del graph，在创建最多约 310 万个 Trie 节点前释放邻接表。 array("I")保存无符号异或值，两个array("i")保存 Trie 儿子。- 条件表达式选择当前位对应的儿子数组。
代码
python
import sys
from array import array
input = sys.stdin.buffer.readline
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
u, v, weight = map(int, input().split())
u -= 1
v -= 1
graph[u].append((v, weight))
graph[v].append((u, weight))
xor_from_root = array("I", [0]) * n
stack = [(0, -1)]
while stack:
node, parent = stack.pop()
for neighbor, weight in graph[node]:
if neighbor != parent:
xor_from_root[neighbor] = xor_from_root[node] ^ weight
stack.append((neighbor, node))
del graph, stack
child_zero = array("i", [0])
child_one = array("i", [0])
def insert(value):
node = 0
for bit in range(30, -1, -1):
children = child_one if value >> bit & 1 else child_zero
if not children[node]:
children[node] = len(child_zero)
child_zero.append(0)
child_one.append(0)
node = children[node]
def maximum_xor(value):
node = answer = 0
for bit in range(30, -1, -1):
wanted = child_zero if value >> bit & 1 else child_one
other = child_one if value >> bit & 1 else child_zero
if wanted[node]:
answer |= 1 << bit
node = wanted[node]
else:
node = other[node]
return answer
insert(0)
answer = 0
for value in xor_from_root[1:]:
answer = max(answer, maximum_xor(value))
insert(value)
print(answer)cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-02
* update_at: 2026-08-02
*/
/* P4551 最长异或路径 */
/* 核心：路径异或 = 两个根前缀异或的异或（根→lca 公共段异或两次抵消）；
* 最大异或对用 01-Trie 逐位贪心：高位支配低位，每层优先走相反位。
* 01-Trie 直接复用 rbook 文章《Trie 字典树》的模板（ALPHA=2, OFFSET='0'），
* 把每个数转成 31 位 0/1 字符串插入；最大异或查询写在模板外部。 */
#include <bits/stdc++.h>
using namespace std;
// 字典树 Trie 模板：插入字符串、判断是否存在、统计前缀出现次数
// 模板参数：ALPHA 字符集大小，OFFSET 字符起点（如 'a'）
// 节点维护 pass(经过次数) 和 end(单词结尾次数)
// 用法：Trie<26,'a'> tr; tr.insert("abc"); tr.contains("abc"); tr.count_prefix("ab");
template <int ALPHA = 26, char OFFSET = 'a'>
struct Trie {
struct Node {
array<int, ALPHA> ch{}; // ch[c] 子节点编号，0 为空（根也是 0）
int pass = 0; // 经过该节点的字符串个数
int end = 0; // 以该节点结尾的完整字符串个数
};
vector<Node> tree; // tree[0] 为根
Trie() { tree.push_back(Node()); }
// 插入 s
void insert(const string &s) {
int u = 0;
tree[u].pass++;
for (char cc : s) {
int c = cc - OFFSET;
if (tree[u].ch[c] == 0) { // 无子节点则新建
tree[u].ch[c] = (int)tree.size();
tree.push_back(Node());
}
u = tree[u].ch[c];
tree[u].pass++;
}
tree[u].end++;
}
// 判断 s 是否完整插入过
bool contains(const string &s) const {
int u = 0;
for (char cc : s) {
int c = cc - OFFSET;
if (tree[u].ch[c] == 0) return false;
u = tree[u].ch[c];
}
return tree[u].end > 0; // 必须作为完整单词结尾
}
// 统计以 prefix 为前缀的字符串个数
int count_prefix(const string &prefix) const {
int u = 0;
for (char cc : prefix) {
int c = cc - OFFSET;
if (tree[u].ch[c] == 0) return 0;
u = tree[u].ch[c];
}
return tree[u].pass;
}
};
const int MAXN = 100000 + 5;
int n; // 节点数
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt;
unsigned int weight_edge[MAXN * 2]; // 边权 < 2^31
unsigned int xor_root[MAXN]; // xor_root[u] = 根到 u 的边权异或
Trie<2, '0'> trie; // 01-Trie：字符集只有 {0,1}
// 把 x 转成 31 位 0/1 字符串（第 30 位到第 0 位），供模板 insert 使用
string to_binary(unsigned int x) {
string s;
for (int bit = 30; bit >= 0; bit--)
s.push_back(((x >> bit) & 1U) ? '1' : '0');
return s;
}
// 查询与 x 异或最大的值，返回最大异或值（模板不含此功能，写在外部）
// 贪心：每层优先走相反位（x 这位是 0 就找 1），走不到才走同一位
unsigned int max_xor(unsigned int x) {
int u = 0;
unsigned int answer = 0;
for (int bit = 30; bit >= 0; bit--) {
int c = (x >> bit) & 1U;
int want = c ^ 1;
if (trie.tree[u].ch[want]) { // 相反位存在：这一位异或得 1
answer |= 1U << bit;
u = trie.tree[u].ch[want];
} else { // 不存在：退而求其次走同一位
u = trie.tree[u].ch[c];
}
}
return answer;
}
void add_edge(int u, int v, unsigned int w) {
edge_cnt++;
to[edge_cnt] = v;
weight_edge[edge_cnt] = w;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void read_input() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
unsigned int w;
cin >> u >> v >> w;
add_edge(u, v, w);
add_edge(v, u, w);
}
}
// BFS 求每个节点的根前缀异或 xor_root[u]
void calc_xor_values() {
queue<int> que;
vector<int> parent(n + 1, 0);
que.push(1);
parent[1] = -1;
xor_root[1] = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
if (v == parent[u]) {
continue;
}
parent[v] = u;
xor_root[v] = xor_root[u] ^ weight_edge[i];
que.push(v);
}
}
}
void solve() {
calc_xor_values();
// 先插入根的前缀 0：这样"单点路径"（u 到根的路径 = pre[u]^0）也被计入，
// 同时 0 的全零路径保证 max_xor 的兜底分支永远走得到。
unsigned int answer = 0;
trie.insert(to_binary(xor_root[1]));
for (int i = 2; i <= n; i++) {
answer = max(answer, max_xor(xor_root[i]));
trie.insert(to_binary(xor_root[i]));
}
cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
树遍历
总结
树上异或题先尝试定义根前缀值；路径问题常会立刻化成普通数组上的异或配对。