## Utopiosphere

引理 1：两张图 $G_1,G_2$ 等价，当且仅当对于任何一个简单环，$G_1,G_2$ 中这个环上边权最大的边是相同的。

引理 2：在图 $G$ 中，对于两条不同的边 $e_1,e_2$，存在一个包含它们的简单环当且仅当它们属于同一点双连通分量。

若一开始 $G$ 的点双连通分量为 $G_1,\ldots,G_k$，那么根据引理 2，不同的点双连通分量是互不影响的，所以我们可以独立分开做，然后将答案乘 $\displaystyle\binom{\sum m_i}{m_1,\ldots,m_k}$，其中 $m_i$ 为 $G_i$ 的边数。

现在考虑一个点双连通的 $G$，设其中边权最大的边是 $e$。由引理 2 知道其余每条边都和 $e$ 共享一个简单环，因此根据引理 1，$e$ 在 $G'$ 中也应当是边权最大的边（否则考虑包含它与边权最大边的环，就矛盾了），所以这条边的边权是固定的。

然后我们将 $e$ 删去，如果 $G$ 依然点双连通，再考虑剩下的边权最大的边；如果 $G$ 分成若干个不同的点双连通分量，那么它们又彼此独立，可以分开做，最后乘一个组合数。

因此整个算法的过程就是：从大到小依次删去 $G$ 的每条边，如果某次删边使得一个点双分成若干点双，那么就将答案乘上这些点双边数的多重组合数。

实现时倒着做，只需考虑加边的过程中维护圆方树。直接做是 $O(n^2)$ 的，也存在 $O(n\log n)$ 做法。

---

附：

引理 1 证明：

必要性：只需考虑将一个环作为子图，最小生成森林就是把这个环边权最大的边去掉，这对于两张图应该是一样的。

充分性：考虑最小生成森林的破圈算法，每次找到任意一个环并删掉边权最大的边，最后就得到最小生成森林。如果条件成立，那么在两张图上执行破圈算法时每次删的都是一样的边，所以最小生成森林形状相同。

引理 2 证明：

必要性：显然。

充分性：根据点双连通图的定义，存在经过任意两点的简单环（因为两点间存在两条点不交路径）。如果在每条边中间加一个点，就可以额外证明：存在经过任意一点 $v$ 和任意一边 $e$ 的简单环。

接下来考虑两个点 $x,y$ 和一条边 $e$。首先求出一个包含 $x,e$ 的简单环 $C$，再找一条 $y\to x$ 的路径 $P$，使得 $C,P$ 的点集的交的大小大于 $1$（如果找不到这样的 $P$，说明 $x$ 是割点，矛盾）。设 $P\cap C$ 的所有点中在 $P$ 上最接近 $y$ 的是 $u$，那么取 $C$ 上的 $x\to u$ 段和 $P$ 上的 $u\to y$ 段，我们就得到了一条经过 $e$ 的 $x\to y$ 路径。

考虑两条边 $e_1,e_2$，其中 $e_1=(x,y)$，先找一条经过 $e_2$ 的 $x\to y$ 路径，再加上边 $e_1$，就得到了经过 $e_1,e_2$ 的简单环。