题解：DLESS R2 T1

喵仔牛奶 · 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)。