BZOJ 3569 DZY Loves Chinese II

Link
随便找一个ST，对每条非树边rand一个\([0,2^{\omega})\)的权值，再令每条树边的权值为所有覆盖它的非树边权值的异或和，这样图不连通当且仅当删掉的边权线性相关。
检查是否线性相关可以利用线性基。
这个算法的正确性大概是\((1-\frac1{2^{\omega}})^{2^k}\)。
代码正在来的路上了。

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12229104.html