把树上路径异或转为两个根前缀异或，再用 01-Trie 求最大异或对。
OJ: luogu
题目 ID: P4551
难度:普及+/提高
标签:01-Trie异或树python
日期: 2026-07-16 19:57
题意
求带权树上任意两点间路径边权异或和的最大值。
思路
令 xor_from_root[u] 为根到 u 的边权异或。两点路径的公共部分异或两次被抵消，因此：
text
xor_path(u, v) = xor_from_root[u] ^ xor_from_root[v]问题变为在所有根前缀异或值中找最大异或对。逐个扫描值，在 01-Trie 中优先走与当前位相反的儿子，查询它与此前值能得到的最大异或，然后插入当前值。
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)复杂度
树遍历
总结
树上异或题先尝试定义根前缀值；路径问题常会立刻化成普通数组上的异或配对。