最大异或路径

题目描述

两个非负整数的 XOR 是指将它们表示成二进制数，再在对应的二进制位进行 XOR 运算。

现在，定义 $K$ 个非负整数 $A_1, A_2, \ldots, A_K$ 的 XOR 和为：

$$A_1 \text{ XOR } A_2 \text{ XOR } \ldots \text{ XOR } A_K$$

问题

考虑一个边权为非负整数的无向连通图，节点编号 $1$ 到 $N$，试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使路径上经过的边的权值的 XOR 和最大。

重要规则：

• 路径可以重复经过某些点或边
• 当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数

输入格式

第一行包含两个整数 $N$ 和 $M$，表示该无向图中点的数目与边的数目。

接下来 $M$ 行描述 $M$ 条边，每行三个整数 $S_i, T_i, D_i$，表示 $S_i$ 与 $T_i$ 之间存在一条权值为 $D_i$ 的无向边。

注意： 图中可能有重边或自环。

输出格式

仅包含一个整数，表示最大的 XOR 和（十进制结果），注意输出后加换行回车。

数据范围

• $N \le 50000$
• $M \le 100000$
• $D_i \le 10^{18}$

输入样例

5 7 
1 2 2 
1 3 2 
2 4 1 
2 5 1 
4 5 3 
5 3 4 
4 3 2 

输出样例

6

样例解释

图结构

节点：1, 2, 3, 4, 5

边：

1. 1-2: 权值2
2. 1-3: 权值2
3. 2-4: 权值1
4. 2-5: 权值1
5. 4-5: 权值3
6. 5-3: 权值4
7. 4-3: 权值2

寻找最大异或路径

目标是找到从1到N=5的路径，使得路径上边权的异或和最大。

考虑路径：1 → 3 → 5 → 4 → 2 → 5 边权：2, 4, 3, 1, 1 异或和：2 ⊕ 4 ⊕ 3 ⊕ 1 ⊕ 1

• 2 ⊕ 4 = 6
• 6 ⊕ 3 = 5
• 5 ⊕ 1 = 4
• 4 ⊕ 1 = 5

得到5，但不是最大的。

实际上，最优路径的异或和为6。

关键观察

路径可重复的性质

由于路径可以重复经过点和边，我们可以利用以下性质：

对于任意无向连通图，从节点 $u$ 到节点 $v$ 的任意一条路径的异或和，可以通过以下方式得到：

设 $P(u)$ 表示从节点 $1$（起点）到节点 $u$ 的任意一条路径的异或和。

那么从 $u$ 到 $v$ 的任意路径的异或和可以表示为：

$$P(u) \oplus P(v) \oplus (\text{环的异或和})$$

特别地，如果我们只考虑简单路径（不重复边），那么从 $u$ 到 $v$ 的异或和就是 $P(u) \oplus P(v)$。

环的作用

当我们允许重复经过边时，我们可以添加任意环到路径中。如果环的异或和为 $c$，那么添加这个环会使总异或和变为原异或和 ⊕ $c$。

因此，问题转化为：

1. 计算从1到每个节点的任意一条路径的异或值 $P(i)$
2. 找到所有环的异或值，构成一个线性空间
3. 在 $P(1) \oplus P(N) = 0 \oplus P(N) = P(N)$ 的基础上，用环的异或值进行最大化

线性基

我们需要从所有环的异或值中构造一个线性基，然后求 $P(N)$ 与线性基中元素组合的最大异或值。

算法步骤

步骤1：计算 $P(i)$

从节点1开始DFS或BFS，计算从1到每个节点的任意一条路径的异或值。

• 初始化 $P(1) = 0$
• 对于边 $(u, v, w)$，如果 $v$ 未被访问，则 $P(v) = P(u) \oplus w$
• 如果 $v$ 已被访问，那么找到了一个环，环的异或值为 $P(u) \oplus P(v) \oplus w$

步骤2：构建线性基

将所有找到的环的异或值插入线性基中。

线性基支持以下操作：

1. 插入：将一个数插入线性基
2. 查询最大值：给定一个数 $x$，求 $x$ 与线性基中若干数的最大异或值

步骤3：计算答案

设 $ans = P(N)$，然后用线性基优化 $ans$：

• 从高位到低位考虑
• 如果 $ans$ 的第 $i$ 位是0，而线性基中第 $i$ 位有值，则 $ans = ans \oplus base[i]$
• 这样能保证 $ans$ 的每一位尽可能为1

线性基实现

struct LinearBasis {
    vector<long long> base;
    
    LinearBasis() : base(61, 0) {}  // 2^60 > 10^18
    
    void insert(long long x) {
        for (int i = 60; i >= 0; i--) {
            if (!(x >> i)) continue;
            if (!base[i]) {
                base[i] = x;
                break;
            }
            x ^= base[i];
        }
    }
    
    long long query_max(long long x) {
        long long res = x;
        for (int i = 60; i >= 0; i--) {
            if ((res ^ base[i]) > res) {
                res ^= base[i];
            }
        }
        return res;
    }
};

示例详细计算（输入样例）

步骤1：计算 $P(i)$

从节点1开始DFS：

1. 1→2 (权2): $P(2) = 0 ⊕ 2 = 2$
2. 1→3 (权2): $P(3) = 0 ⊕ 2 = 2$
3. 2→4 (权1): $P(4) = 2 ⊕ 1 = 3$
4. 2→5 (权1): $P(5) = 2 ⊕ 1 = 3$
5. 发现环：
   • 边4-5 (权3): 环值 = $P(4) ⊕ P(5) ⊕ 3 = 3 ⊕ 3 ⊕ 3 = 3$
   • 边5-3 (权4): 环值 = $P(5) ⊕ P(3) ⊕ 4 = 3 ⊕ 2 ⊕ 4 = 5$
   • 边4-3 (权2): 环值 = $P(4) ⊕ P(3) ⊕ 2 = 3 ⊕ 2 ⊕ 2 = 3$

步骤2：构建线性基

插入环值：3, 5, 3

• 插入3（二进制011）
• 插入5（二进制101）：5 ⊕ 3 = 6（二进制110），插入6
• 插入3：3已经在线性基中（3 ⊕ 6 = 5，5 ⊕ 3 = 6，最终变为0）

线性基：{3, 6}

步骤3：计算答案

$P(N) = P(5) = 3$（二进制011）

用线性基优化：

• 3 ⊕ 6 = 5（二进制101）> 3，所以取5
• 5 ⊕ 3 = 6（二进制110）> 5，所以取6
• 最终答案：6

输出：6

正确性证明

关键定理

对于无向连通图，从节点 $u$ 到节点 $v$ 的所有可能路径的异或和构成的集合为：

$$\{P(u) \oplus P(v) \oplus x \mid x \in S\}$$

其中 $S$ 是由所有环的异或值生成的线性空间，$P(i)$ 是从1到 $i$ 的任意一条路径的异或值。

证明思路

1. 任意路径可以分解为：从 $u$ 到 $v$ 的一条简单路径 ⊕ 若干个环
2. 环的异或值构成线性空间
3. 因此最大化问题转化为：在 $P(u) \oplus P(v)$ 的基础上，用环的线性基最大化异或值

时间复杂度

1. DFS/BFS遍历图：$O(N + M)$
2. 线性基操作：每次插入 $O(\log D_i)$，最多 $M$ 次
3. 总复杂度：$O(N + M \log D_{\max})$，可以接受

注意事项

1. 边权范围：$D_i \le 10^{18}$，需要 long long 类型
2. 图可能不连通：但题目说是连通图
3. 重边和自环：需要正确处理
4. 线性基大小：由于 $D_i \le 10^{18} < 2^{60}$，线性基需要60位

为什么可以重复经过边

重复经过边相当于在路径中添加一个"往返"：

• 从 $u$ 到 $v$ 再回到 $u$
• 异或和为：$w ⊕ w = 0$
• 所以重复经过边偶数次不改变异或和，奇数次相当于经过一次

更重要的是，通过重复经过边，我们可以添加任意环到路径中，从而利用环的异或值优化结果。

时空限制

• 时间限制：1秒
• 空间限制：64MB