首页 > 代码库 > 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 (并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。