loj6157 A^B Problem (并查集)

发布时间:2017-7-9 7:36:20编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"loj6157 A^B Problem (并查集) ",主要涉及到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

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


上一篇:OkHttp上传文件,服务器端请求解析找不到文件信息的问题

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款