CF1236F Alice and the Cactus

Alice 最近在她家附近发现了一些仙人掌！几个月后，越来越多的仙人掌出现，很快就堵住了道路。因此，Alice 想要清除它们。 [仙人掌](https://en.wikipedia.org/wiki/Cactus_graph)是一种连通的无向图。该图中的每条边至多只属于一个简单环。我们称图中一组不同节点 $x_1, x_2, \ldots, x_k$ 构成一个简单环，如果 $k \geq 3$ 且所有节点对 $x_1$ 和 $x_2$、$x_2$ 和 $x_3$、$\ldots$、$x_{k-1}$ 和 $x_k$、$x_k$ 和 $x_1$ 都通过边相连。边 $(x_1, x_2)$、$(x_2, x_3)$、$\ldots$、$(x_{k-1}, x_k)$、$(x_k, x_1)$ 都属于这个简单环。 仙人掌太多了，似乎很难将它们全部清除。但 Alice 有魔法。当她施展魔法时，仙人掌中的每个节点都会以 $\frac{1}{2}$ 的概率被独立移除。当一个节点被移除时，与之相连的所有边也会被移除。 现在 Alice 想要测试她的魔法。她选中了一个有 $n$ 个节点和 $m$ 条边的仙人掌。设 $X[S]$（其中 $S$ 是被移除节点的集合）为移除集合 $S$ 中的节点后，剩余图中的连通块数量。在施展魔法前，她想知道随机变量 $X$ 的[方差](https://en.wikipedia.org/wiki/Variance)，其中图中每个节点都有 $\frac{1}{2}$ 的概率被移除，且这 $n$ 个事件彼此独立。根据定义，方差等于 $E[(X - E[X])^2]$，其中 $E[X]$ 是 $X$ 的[期望值](https://en.wikipedia.org/wiki/Expected_value)。请帮助她计算这个值，并对 $10^9+7$ 取模。 形式化地，设 $M = 10^9 + 7$（一个质数）。可以证明，答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数，且 $q \not\equiv 0 \pmod{M}$。输出等于 $p \cdot q^{-1} \bmod M$ 的整数。换句话说，找到一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

第一行包含两个整数 $n$ 和 $m$，用空格分隔（$1 \leq n \leq 5 \times 10^5,\, n - 1 \leq m \leq 5 \times 10^5$）——仙人掌的节点数和边数。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$，用空格分隔（$1 \leq u, v \leq n,\, u \neq v$），表示节点 $u$ 和 $v$ 之间有一条边。 保证图中没有自环和重边，且给定的图是仙人掌。

输出一个整数，表示在每个节点以 $\frac{1}{2}$ 的概率独立被移除后，剩余图中连通块数量的方差。答案需对 $10^9+7$ 取模。

在第一个样例中，答案为 $\frac{7}{64}$。如果所有节点都被移除，则 $X$ 的值为 $0$，否则为 $1$。因此，$X$ 的期望为 $0\times\frac{1}{8}+1\times\frac{7}{8}=\frac{7}{8}$。所以，$X$ 的方差为 $(0 - \frac{7}{8})^2\times\frac{1}{8}+(1-\frac{7}{8})^2\times\frac{7}{8} = (\frac{7}{8})^2\times\frac{1}{8}+(\frac{1}{8})^2\times\frac{7}{8} = \frac{7}{64}$。 在第二个样例中，答案为 $\frac{1}{4}$。 由 ChatGPT 4.1 翻译