自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 23:18:15，当前版本为作者最后更新于2025-05-16 22:33:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

显然，$i$ 的点权 $a_i=b_{i,i}$。

考虑一对 $(i,j)$：

• 若 $a_i\oplus a_j\neq b_{i,j}$，则必然不存在 $(i,j)$ 这条边。
• 若 $a_i\oplus a_j=b_{i,j}$，则必然存在 $(i,j)$ 这条边。若不存在，$i\to j$ 路径长度 $\ge 3$，则路径去掉 $i,j$ 两个点至少有一个点，而路径上点权的异或和为 $b_{i,j}\oplus a_i\oplus a_j=0$，不符合题意。

由于保证有解，直接输出所有 $a_i\oplus a_j=b_{i,j}$ 的对即可。

复杂度 $\mathcal O(\sum n^2)$。