先叠个盾，我觉得这不算讨论区题解，只是想对一处比较重要的细节做补充说明。本人在这个细节卡了两天，希望可以节约后人的时间。

$\oplus$ 代表异或。

这里通篇只讲第一层那个完全图的优化建图，而且 $C$ 显然一直没什么影响（无非就是给所有最短路都乘个 $C$）。所以，整篇都会忽略第二层他直接给的边，以及 $C$ 的影响。

回忆一下建图优化

本题的优化建图是这样的：

对一条边 $(u, v, u \oplus v)$，设 $u \oplus v$ 中二进制位为 $1$ 的位数分别为 $k_1$，$k_2$，$k_3$，……，$k_K$。

则这条边在 $K \ne 1$ 时，等效于下面的一条路径，从而使得 $(u, v)$ 这条边可以删去：

• 从 $u$ 出发，按照 $2^{k_1}$ 的权值，会走到 $u \oplus 2^{k_1}$；
• 从 $u \oplus 2^{k_1}$ 出发，按照 $2^{k_2}$ 的权值，会走到 $u \oplus 2^{k_1} \oplus 2^{k_2}$；
• 从 $u \oplus 2^{k_1} \oplus 2^{k_2}$ 出发，按照 $2^{k_3}$ 的权值，会走到 $u \oplus 2^{k_1} \oplus 2^{k_2} \oplus 2^{k_3}$；
• ……
• 从 $u \oplus 2^{k_1} \oplus 2^{k_2} \oplus \ldots \oplus 2^{k_{K-1}}$ 出发，按照 $2^{k_K}$ 的权值，会走到 $u \oplus 2^{k_1} \oplus 2^{k_2} \oplus \ldots \oplus 2^{k_K} = u \oplus (u \oplus v) = v$。

$K \ne 1$ 的边被拆成了若干条 $K = 1$ 的边构成的路径，所以我们只需要保留原图中 $K = 1$ 的边。这就是本题的建图优化。

问题

然而，上面构造的路径有一个问题，我们不能保证中转点 $\in [1, n]$。

举个例子：$n = 6 = (110)_2$，$u = 3 = (011)_2$，$v = 5 = (110)_2$。

$u \oplus v = (101)_2$，则 $k_1 = 2$，$k_2 = 0$。

根据规则，我们从 $u = (011)_2$ 开始，按照 $2^{k_1}$ 的权值走到 $(011)_2 \oplus 2^{2} = (111)_2$，会发现这个中转点 $> n$。

事实上，按照上面的构造，我们只能保证，设 $s$ 为满足 $2^s > n$ 的最小值，则中转点不会超过 $[0, 2^s - 1]$。

至于这是为什么，假设 $n = (001\ldots)_2$，则 $n$ 二进制最高位那个 $1$，正好是第 $s - 1$ 位。不难发现，$u \le n$，$v \le n$，因此 $u$ 和 $v$ 在第 $s$ 位及以上一定都是 $0$，所以 $u \oplus v$ 在第 $s$ 位以上也都是 $0$，使得任意 $k_i$ 都有 $k_i < s$。

所以中转过程中，中转点的第 $s$ 位及以上始终都是 $0$。因此，中转点一定小于等于 $(0011\ldots1)_2$，其中最高位 $1$ 为第 $s - 1$ 位。

另外注意，中转点还可能取到 $0$。

解决方案一

解决方案一：

设 $s$ 为满足 $2^s > n$ 的最小值。

在最后，我们将所有满足 $u < 2^s$，$k < s$ 的 $(u, u \oplus 2^k, 2^k)$ 全部建好（显然 $u \oplus 2^k < 2^s$）。

这样以来，建出的边的端点可能会超过 $n$，或等于 $0$，只保证不会取到 $2^s$ 及以上。

---

这种优化建图方式，相当于在原图基础上，

• 凭空增加了一些点和一些边。
• 删除了所有 $K \ne 1$ 的边。

我们需要保证，这种优化不会使得 $[1, n]$ 之内任意两点间的最短路有变化。

第二步是不会影响最短路的，因为我们已经证明，一条 $(u, v)$ 如果满足 $K \ne 1$，由于 $K =1$ 边的存在，删去这条边之后，$u$ 和 $v$ 之间仍然至少存在一条权值和小于等于 $u \oplus v$ 的路径，因此必定不会影响 $u$ 和 $v$ 之间的最短路。

那么，我们还需要证明，第一步凭空增加的点和边不会影响最短路。

那么这就涉及到原来这层完全图的一个性质了：

任何一对 $\boldsymbol s$，$\boldsymbol t$，其最短路必定是 $\boldsymbol{s \oplus t}$。

我们用二进制修改的思想，观察 $u$ 通过 $(u, v, u \oplus v)$ 这条边一次走到 $v$。

假设 $u$ 和 $v$ 不同的二进制位数分别是 $k_1$，$k_2$，……，$k_K$，那么上面这一步操作，就相当于花费 $2^{k_1} + 2^{k_2} + \ldots + 2^{k_K}$ 的距离代价，使得 $u$ 的二进制第 $k_1$，$k_2$，……，$k_K$ 都分别反转，从而让 $u$ 变成 $v$。

因此，从 $s$ 出发，通过一些边连续走到 $t$ 的过程，可以看做通过不断反转 $s$ 的一些二进制位，让 $s$ 变成 $t$ 的过程，而反转 $s$ 的第 $k$ 位，代价是 $2^k$。

于是问题变成这样：

给定 $s$，$t$，可以进行任意次操作，每一次你可以选择若干个 $k_1$，$k_2$，……，$k_K$，花费 $2^{k_1} + 2^{k_2} + \ldots + 2^{k_K}$ 的代价将 $s$ 的第 $k_1$，$k_2$，……，$k_K$ 位分别反转，使得 $s$ 变成 $t$。

相信聪明的你看出来了，为了让代价最小，显然，我们只需要反转 $s$ 和 $t$ 中，二进制不同的那些位，而且每一位只用反转一次。这样以来就可以得到最小代价 $s \oplus t$。

通过二进制反转的思想也更容易理解本题的优化建图。显然，从 $u$ 到 $v$，你可以直接一次性使用若干个 $k$ 反转得到，也可以拆成若干步，每步只使用一个 $k$ 反转得到。因此，我们只需要保留 $2^k$ 边权的那些边，从而保留最基本的从每一个数开始反转任意一位的功能即可。

所以这题 $M = 0$ 的数据梯度是这么来的：直接输出 $A \oplus B$ 即可。

【性质证明结束】

有了这个性质，我们容易发现，因为我们加出来的边本质也是付出相应代价的二进制位反转功能，不影响上面的证明，也就自然不影响任意两点 $u$，$v$ 之间的最短路，它一定是 $u \oplus v$。

所以，这种建图优化是对的。要注意这种方式中，建图中表示点大小的数组大小常量要开的比 $\max(N) = 10^5$ 大，参考应该是 $2^{17} = 131072$ 这个比 $\max(N)$ 大的最小的二的幂。

解决方案二

解决方案二：

在最后，我们将所有满足 $u \le n$，$u \oplus 2^k \le n$ 的 $(u, u \oplus 2^k, 2^k)$ 全部建好。

这样以来，不在 $[1, n]$ 内的端点只会取到一个 $0$。

---

先说结论，这种优化其实也是对的，但没有题解解释为啥。

还记得这个例子吗？

举个例子：$n = 6 = (110)_2$，$u = 3 = (011)_2$，$v = 5 = (110)_2$。

$u \oplus v = (101)_2$，则 $k_1 = 2$，$k_2 = 0$。

根据规则，我们从 $u = (011)_2$ 开始，按照 $2^{k_1}$ 的权值走到 $(011)_2 \oplus 2^{2} = (111)_2$，会发现这个中转点 $> n$。

看似这种会走到超过 $n$ 中转点的方式，其实你只需要改动一下 $k_i$ 的顺序就能解决。

还是这个例子：

举个例子：$n = 6 = (110)_2$，$u = 3 = (011)_2$，$v = 5 = (110)_2$。

$u \oplus v = (101)_2$，

但这次，我们让 $k_1 = 0$，$k_2 = 2$。看一下会发生什么：

根据规则，我们从 $u = (011)_2$ 开始，按照 $2^{k_1}$ 的权值走到 $(011)_2 \oplus 2^{0} = (010)_2$，怎么样，这次中转点是不是没超过 $n$？

然后我们再按照 $2^{k_2}$ 的权值，走到 $(010)_2 \oplus 2^{2} = (110)_2$，目标达成。

事实上，任何一对 $s$，$t$，在优化后的图中，都一定存在一种长度为 $s \oplus t$ 的路径。即，一定存在 $k_i$ 的一种排列，使得中转点始终不超过 $n$。

这是怎么做到的？其实很简单，我们仍然沿用二进制修改的思想。

我们现在只看 $K=1$ 的边，那么 $u$ 通过边权为 $2^k$ 的边走到 $v$ 的过程，可以看做 $u$ 的二进制第 $k$ 位被修改。

那么从 $s$ 连续走到 $t$ 的过程，可以看做连续修改 $s$ 中二进制的每一位，使得最终变成 $t$。只要我们只修改 $s$ 和 $t$ 中二进制不同的那些位各一次，就能做到路径长度 $s \oplus t$ 了。

比如上面这个例子可以形式化地表示如下：

011 -> 010 -> 110

那么，只要我们规定一下修改的顺序，先将所有要修改的 1 修改成 0，再将所有要修改的 0 修改成 1，我们就一定能使得 $s$ 连续变换到 $t$ 的过程中，中转点始终不超过 $\max(s, t)$。

证明特别简单。你把一个数的二进制一位 1 修改成 0，肯定是在把这个数变小吧？0 修改成 1 同理。所以上面这个修改顺序，使得 $s$ 先单调变小，然后再单调变大成 $t$，整个过程不超过 $\max(s, t)$ 是十分自然的。

另外，变小和变大之间的极值点是 $s \operatorname{bitand} t$，其中 $\operatorname{bitand}$ 代表位运算与。这也不难理解吧。

所以，即使你只建端点在 $n$ 以内的 $K=1$ 边，同样合理。只要任何一个 $K \ne 1$ 边 $(u, v, u \oplus v)$ 满足删除这条边后，$u$ 到 $v$ 仍然存在一条长度小于等于 $u \oplus v$ 的路径就可以了，显然我们做到了。

这个做法还会涉及到点 $0$。可以根据解决方案一中那个多建点建异或权值边不会影响的证明，来说明这个不会影响。

也可以直接想一下 $0$，显然 $u \oplus 0 + 0 \oplus v = u + v \ge u \oplus v$，所以肯定不会影响最短路的。