BZOJ 3563/3569 DZY Loves Chinese

发布于 2017-11-27  121 次阅读


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

题意:无向图,删边后判断连通性(删后复原),强制在线。


3563 那题强制在线是假的,能推出来答案那种...

考虑怎么做靠谱点:

首先可以有一个思路是任求一棵生成树,边权均为 1,非树边就链上边权加一,每次减掉给出的边后看看有没有边的边权被减到零,可以用链剖或者 lct 什么的做。

发现其实没法做,复杂度会炸。

于是构造一下,每条非树边随机给定一个权值,树边权值为覆盖它的非树边的异或和。

那么不联通的条件当且仅当至少有一条树边满足它被切断且覆盖它的非树边均被切断,即切断的边中有一个子集的异或和为零。

即线性无关,线性基判即可。这份代码交 3563 的话需要将 k 也 xor 一下 ans

 


一个非常弱的准退役OIER