自动搬运

查看原文

来自洛谷，原作者为

	sevenki 心有所冀，毕生求溯。

搬运于2025-08-24 22:54:26，当前版本为作者最后更新于2024-01-21 09:40:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

tag: 随机赋权、线性基（不是必须的）

大概是比较有意思的题目。

但是，这是一道原题。Luogu P5227

这道题的难点主要在于：

• 想到随机赋权。
• 知道怎么赋权。

在赛场上原题面的数据范围下，这道题读入估计得花 $1$ 个月。

后来出题人把 $c$ 的数据范围改成和原题一模一样。

思路

下面说本题做法。

随机赋权，使删去一些边，使得图刚好不联通的边集的权值异或值为 $0$。

“刚好不联通” 指的是，少删任意一条都能连。

怎么办呢？

我们考虑几个简单情况。

对于一个点，把所有和他相关的边切掉，图就不联通了。因此，一个点的所有连边的异或值为 $0$。

如果按照这个方法赋权，那么：

对于一个联通的点集，与外界（两点非联向该点集的边）的边权异或值将会是什么？

每个点连的边的异或值为 $0$。点集里，每个点都按照这样算一次，异或值显然为 $0$。

此时，联向外面的边由于一端联向点集中，因此被计算 $1$ 次。 联向里面的边由于 $2$ 端联向点集中，因此被计算 $2$ 次，直接就抵消了。

那么结果其实就是联向外面的边权异或值。而结果为 $0$。

于是，只要能构造出“一个点的所有连边的异或值为 $0$” 的图，问题就解决了。

构造方法：

随便来一棵生成树。

对于图中不在树上的边，随机赋权。

父亲联向孩子的边，就是孩子的除了联向父亲之外其余边的异或和。

这样子就能保证每个点的所有连边的异或值为 $0$。

由于权值随机，所以不符合条件，异或值却恰恰为 $0$ 的概率比较小。这样子我们就从概率上解决了这个问题。

注意，出错的概率随着 $c_i$ 增大而增大。这个问题在后面会有细致的说明。

解决询问

对于每次询问，如果其中任意几条边的异或和为 $0$，那么把它们删掉图就不联通。

如果暴力枚举边集，复杂度就会达到 $2^c$。然而，在 $c\leq 4$ 的情况下，暴力枚举的方法跑的飞快。

如何才能去掉这个指数，使得 $c$ 的范围可以更大？

我们可以考虑线性基。

用线性基可以在 $O(c \log w)$ 的时间内判断几个数中是否有异或和为 0 的组合。

线性基可以动态插入，也可以高斯消元。前者容易写得多。

这样子，我们就可以在时间上通过 $\sum c \log w$ 的数据。不保证正确性。 我的意思是，在 $c$ 大的情况下，正确性几乎为 $0\%$。

关于概率

为什么我们的随机算法不能通过 $c$ 很大的数据？

先看线性基的重要性质：

• 线性基中没有异或和为 $0$ 的子集。
• 线性基中各数二进制最高位不同。

显然，如果前面的几个数构造的线性基把 $64$ 个位置占满了，那么后面的数就不会再增加新的线性基元素。

如果没有插入到任何一个位置上，则表明该数可以由线性基中若干个元素的异或和表示出。也就可以用原来的元素异或出。

那么该数与线性基中这若干个元素的异或和为 $0$。

这样子的话，当 $c\ge \log w$，无论删的是什么边都可以使得异或和都为 $0$。

那么我们的概率正确就被打破了。

比如，有一个环。$i\to i+1\bmod n$。

在这里面随便多连几条边。

我们询问把这多连的边删掉图连不联通，答案显然为 $1$。

但是如果询问的边数量大的话，则可以使得异或和为 $0$ 了。

而我们定义异或和为 $0$ 表示删掉这几条边图不联通。显然发生了矛盾。

所以这就是上述问题的 $ans$。

另外，还有一个很重要的性质：

$c$ 在小于 $\log w$ 的情况下，越大，出错概率越大。

感性理解一下，随着数的增多，异或出来的数的数量也越来越多，越有可能碰到 $0$，这时随机赋权就越有可能出错（使得删掉一些边而图联通时这些边的异或值却为 $0$）。

参考

本人不太会表述，且不太清楚线性基原理，所以本文有一些内容参考了：

• 线性基学习笔记 Menci's OI Blog
• OI wiki 线性基

外话

了解一个算法、定理的本质还是很重要的。

如果不了解线性基本质，就无法发现我上面说的概率问题。

感谢偶然的发现，让我意外的学到了不少。