bzoj 4644: 经典傻逼题 线段树分治+线性基

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4644


一条边的两个端点只能选其中之一,如果两个都选,这条边就没有贡献了。

这不就是异或么?

所以我们把每条边的权值异或到点上,然后用线段树维护时间,把每条边所影响的时间都找出来,在线段树中标记出来,然后在线段树上进行dfs,由于线性基不能回溯,所以我们每次下传的时候带着线性基一起下传(就相当于复制一个),因为是对时间维护的线段树,所以扫到叶子节点时就可以输出了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注