考虑边权转点权,让边权满足其为相邻点权的异或和,操作变成交换两个点的点权。
随便钦定一个为根,设 d
i
为初始时 i 的点权,f
i
是 i 期望得到为多少。如果存在 d,f,满足它们是相同的集合,就有解。
注意到如果确定了一个点的点权,那么其他所有点权都能唯一的确定。
现在钦定 f
i
为 i 到根路径上的边权和(或者说钦定 f
1
=0),注意到任何一组解都能把所有点权异或 f
1
,得到 f
1
=0 的解,所以判断是否有解就判断 f
1
=0 的时候是否有解。
现在 f 确定了,看是否存在 d,满足 d 和 f 是相同的集合。
现在继续钦定 d
i
为 i 到根路径上边权和,与 f 相同,所有可能为答案的 d
′
都是 d 异或上一个 x 得到的。
那么有解的必要条件就是 (d
1
⊕x)⊕(d
2
⊕x)⊕...⊕(d
n
⊕x)=f
1
⊕f
2
⊕...⊕f
n
,由于 n 为奇数,所以可以解出 x 是多少。
由于这仅是必要条件,那么最后还要 check 一下是否合法。