首页 > 代码库 > loj6157 A^B Problem (并查集)

loj6157 A^B Problem (并查集)

题目:

https://loj.ac/problem/6157

分析:

这种树上异或,一般是采用分位考虑,但是这题即使分位,也会发现非常不好处理

这里考虑维护一个点到其根的路径的异或值

用并查集去检测m个测试

若s和t不在一个并查集内:

  挑出s的根f1,t的根f2,father[f1]=f2,并且发现w[f1]=c^w[s]^w[t]

若s和t在一个并查集内:

  那么首先这个并查集内的所有点的w值都已经求过了,那么只要check一下c是否等于w[s]^w[t]即可

如果最后并查集数量多于一个,那么就是No

直接遍历一遍找最小的和最大的就行

loj6157 A^B Problem (并查集)