XOR（异或）是一种二元逻辑运算，其运算结果当且仅当两个输入的布尔值不相等时才为真，否则为假。 XOR 运算的真值表如下（ 表示真， 表示假）：
| 输入 |
输出 |
| A |
B |
A XOR B |
| 0 |
0 |
| 1 |
1 |
| 1 |
0 |
| 1 |
0 |
而两个非负整数的 XOR 是指将它们表示成二进制数，再在对应的二进制位进行 XOR 运算。
容易验证， XOR 运算满足交换律与结合律，故计算若干个数的 XOR 时，不同的计算顺序不会对运算结果造成影响。从而，可以定义 个非负整数 ，，……，，的 XOR 和为
XOR XOR …… XOR XOR
考虑一个边权为非负整数的无向连通图，节点编号为 到 ，试求出一条从 号节点到 号节点的路径，使得路径上经过的边的权值的 XOR 和最大。
路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数，具体见样例。
