首页 > 其他 > 详细

loj6157 A^B Problem (并查集)

时间:2017-07-01 20:44:18      阅读:307      评论:0      收藏:0      [点我收藏+]

题目:

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 (并查集)

原文:http://www.cnblogs.com/wmrv587/p/7103321.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!