广义串并联图小计

引入

对于一个无向图，我们可以通过如下三种操作缩小规模：

• 删一度点：把度数为一的点删掉

• 缩二度点：把度数为二的点缩成一条边

• 叠合重边：把两条重边合并

可以证明，对于满足 \(m-n\leq k\) 的连通图，通过以上操作可以使得新图点数 \(\leq 2k\)，边数 \(\leq 3k\) ，且我们仔细分析一下可以发现：

• 新图内的每条边代表了原图一个连通子图，且该子图与剩余部分只有两个点相连，我们称之为 界点

• 新图内的每个点代表了原图若干个连通子图，且每个连通子图与只和该点有边

特别的，如果最终只剩下了一个点，那么称该图为 广义串并联图 。

[SNOI2020] 生成树

仙人掌加上一条边之后一定是一个广义串并联图，我们考虑维护上述三种操作。

对与每条边，维护 \(f_e,g_e\) 表示：该边代表的连通子图的左右界点连通/不连通的方案数，\(ans\) 表示总答案。

• 删一度点：被删除的点代表的连通块之后就没用了，我们让 \(ans=ans*f_e\)

• 缩二度点：设该二度点的两条边分别为 \(e_1,e_2\) ，那么：

• • \(f=f_{e_1}f_{e_2}\)
• • \(g=f_{e_1}g_{e_2}+g_{e_1}f_{e_2}\)

• 叠合重边：设重合的两条边分别为 \(e_1,e_2\) ，那么

• • \(f=f_{e_1}g_{e_2}+g_{e1}f_{e2}\)
• • \(g=g_{e_1}g_{e_2}\)

复杂度可以做到 \(O(n+m)\)

AClink

[HNOI/AHOI2018] 毒瘤

对于每条边 \(e\) ，设 \(f_{e,0/1,0/1}\) 代表与边 \(e\) 相连的两个点选的状态是 \(0/1,0/1\) 时，该边对应的连通子图内的方案数，\(g_{x,0/1}\) 代表 \(x\) 的状态时 \(0/1\) 时通过 删一度点 操作挂在 \(x\) 上的子图内的方案数，那么上述三操作对应的 \(f\) 和 \(g\) 的转移是简单的。

最后剩下的图中不超过 \(20\) 个点，我们 \(2^{20}\) 枚举然后把系数乘起来就好了。

复杂度 \(\Theta(n\log n+2^{20}\times 30)\) ，跑不满。

AClink

[集训队互测2024]最短路求和

数据范围明示了要用这个东西。

我们先把一度点删掉，现在图里每个点可以代表好几个点。

把剩下的图里，度数 \(>2\) 的点称为关键点，那么有不超过 \(2000\) 个关键点，两个关键点之间有若干链。

我们先 \(O(n^2\log n)\) 预处理关键点之间的最短路，考虑剩下的分为同一条链上的最短路和不在同一条链上的最短路，我们枚举一条链上一个点，另一半一定一个前缀是走左边，一个后缀是走右边，且类似莫队暴力维护这个分界点复杂度均摊就是对的。

因此复杂度 \(O(k^2\log k+kn)\)

AClink