问题分析

题目给定一个无向连通图 ( G )，已知 ( G ) 在删除任意一条边后会变成一个仙人掌图（即没有两个环共享一条边的连通图）。要求计算 ( G ) 的生成树个数，并对结果取模 ( 998244353 )。

关键思路

1. 生成树计数：

   • 生成树的计数通常可以通过矩阵树定理（Matrix-Tree Theorem）来计算，但对于大规模图（如 ( n \leq 5 \times 10^5 )），直接应用矩阵树定理是不现实的。
   • 本题的特殊性质（删除一条边后是仙人掌）允许我们采用更高效的收缩方法。

2. 仙人掌图的性质：

   • 仙人掌图的生成树计数可以通过环的贡献来计算。具体来说，每个环的生成树数目是该环的长度（因为需要断开一条边）。
   • 由于原图删除一条边后是仙人掌，说明原图最多有一个“非仙人掌”结构（如两个环共享一条边）。

3. 边收缩方法：

   • 采用贪心策略，每次选择度数最小的节点进行收缩：
     • 如果节点的度数为1，直接收缩其唯一邻边，并累乘该边的贡献。
     • 如果节点的度数为2，合并其两条邻边，并按照动态规划的方式更新边的属性 ( f ) 和 ( g )。
   • 边的属性 ( f ) 和 ( g ) 分别表示某种组合贡献，具体更新规则如下：
     • 合并两条边时，( f_{\text{new}} = f_1 \cdot f_2 )，( g_{\text{new}} = f_1 \cdot g_2 + g_1 \cdot f_2 )。
     • 如果两条边已经存在，则进一步合并 ( f ) 和 ( g ) 的值。

4. 动态维护度数：

   • 使用 set 维护节点的度数，确保每次能快速找到度数最小的节点进行收缩。

算法流程

1. 初始化：

   • 读取图的边，初始化每条边的 ( f = 1 )、( g = 1 )（表示初始贡献）。
   • 将所有节点按度数插入 set。

2. 收缩过程：

   • 不断取出度数最小的节点 ( u )：
     • 如果 ( u ) 的度数为1，直接收缩其邻边，并更新结果 ( ans )。
     • 如果 ( u ) 的度数为2，合并其两条邻边，并更新边的属性 ( f ) 和 ( g )。
   • 更新相关节点的度数信息。

3. 结果计算：

   • 当图中只剩下一个节点时，( ans ) 即为生成树的数目。

复杂度分析

• 时间复杂度：( O(m \log n) )（每次操作涉及 set 的插入和删除）。
• 空间复杂度：( O(n + m) )（存储图的邻接表）。

总结

本题通过贪心收缩度数最小的节点，并结合动态规划维护边的属性，高效地计算出生成树的数目。利用仙人掌图的性质，避免了直接使用矩阵树定理的高复杂度，适用于大规模图的计算。