如果你有一个序列上的问题，可以尝试将其放在树上。
如果你有一个树上的问题，可以尝试将其放在仙人掌[^1]上。
如果你有一个仙人掌上的问题，可以尝试将其放在广义串并联图上。
广义串并联图
定义
不存在同胚于 $K_4$ 的子图的无向图。即，对于任意 $4$ 个点，不能存在下图：
串联与并联
其实也可以借助电路来理解。广义串并联图只能通过下述 $3$ 种方法生成（最开始有一个点，电源）：
-
增加新的用电器。即从一个已有的点 $u$ 上建边 $(u,v)$，增加点 $v$。
-
在串联电路上增加用电器。即在边 $(u,v)$ 上增加点 $x$，删除 $(u,v)$，增加 $(u,x),(x,v)$。
-
并联。即对于 $u,v$ 连通，增加边 $(u,v)$。
常见的树、基环树、仙人掌都是广义串并联图。太好了不用学仙人掌了。
性质
对于一个 $n$ 个点，$m$ 条边的一般图，若 $m-n\leq k$，可以通过广义串并联图方法将原图缩为一个满足 $n\leq 2k,m\leq 3k$ 的新图。因此当 $k$ 比较小的时候，可以缩图之后跑暴力。
实现
考虑如何维护缩图的过程。
显然每次需要维护的点都是度数小于等于 $2$ 的点，其余点不用动。并且，我们每次操作的都是「最外层」的点，可以对原图进行一个类似于拓扑排序的操作。
维护一个队列 $q$，初始时将所有度数小于等于 $2$ 的点加入 $q$，之后每次取出队首 $x$ 并弹出。
$x$ 在队列中，说明其度数不大于 $2$：
-
若度数为 $1$，则设其唯一连边的节点为 $v$，将 $x$ 的答案转移到 $v$ 上之后删去边 $(x,v)$。
-
若度数为 $2$，则设其连边为 $(u,x),(x,v)$，需要将其缩二度点转化为 $(u,v)$。
将 $(u,x),(x,v)$ 的答案转移到 $(u,v)$ 后，添加边 $(u,v)$。若 $(u,v)$ 已经存在，还需要叠合重边。
删除之后，如果另一个点度数小于等于 $2$，也要加入队列 $q$。
具体维护上，因为一般都需要维护关于边的信息，因此可以对于每一个点 $x$ 开哈希表存储二元组 $(v,\textit{value})$ 表示边 $(u,v)$ 的信息为 $\textit{value}$。
也可以用 map 维护，复杂度多一个 $\log$。
例题
给定无向连通图 $G$，满足 $G$ 删去一条边后为仙人掌，求 $G$ 的生成树个数对 $998244353$ 取模的结果。
原图满足广义串并联图的定义。
设答案为 $\textit{ans}$，初始时维护 $\textit{ans}=1$。
那么接下来就考虑如何维护三种操作。
设 $f_{e,0/1}$ 表示边 $e$ 选/不选的其对应子图的方案数。
-
删一度点，边为 $e$，那么将 $f_{e,1}$ 乘入答案即可。
-
缩二度点，合并边 $e_1,e_2$ 为 $e$。
$e_1,e_2$ 不可能同时不选（否则 $e$ 不存在），那么则有：
\[\begin{aligned}
f_{e,0}&=f_{e_1,0}f_{e_2,1}+f_{e_1,1}f_{e_2,0}\\
f_{e,1}&=f_{e_1,1}f_{e_2,1}
\end{aligned}\]
-
叠合重边 $e_1,e_2$。$e_1,e_2$ 不可能同时选，等效于一条边 $e$：
\[\begin{aligned}
f_{e,0}&=f_{e_1,0}f_{e_2,0}\\
f_{e,1}&=f_{e_1,0}f_{e_2,1}+f_{e_1,1}f_{e_2,0}
\end{aligned}\]
初始时，$f_{e,0}=f_{e,1}=1$。时间复杂度 $\mathcal O(n)$。
参考代码
```cpp
//#include<bits/stdc++.h>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
constexpr const int N=2e5,P=998244353;
int n;
unordered_map<int,array<int,2>>f[N+1];
array<int,2> twist(array<int,2>a,array<int,2>b){
return {1ll*a[0]*b[0]%P,(1ll*a[0]*b[1]+1ll*a[1]*b[0])%P};
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
if(f[u].count(v)){
f[u][v]=f[v][u]=merge(f[u][v],{1,1});
}else{
f[u][v]=f[v][u]={1,1};
}
}
queueq;
for(int i=1;i<=n;i++){
if(f[i].size()<=2){
q.push(i);
}
}
int ans=1;
while(q.size()){
int x=q.front();q.pop();
if(f[x].size()==1){
auto [v,e]=*f[x].begin();
ans=1ll*ans*e[1]%P;
f[v].erase(x);
if(f[v].size()<=2){
q.push(v);
}
}else if(f[x].size()==2){
auto [u,e1]=*f[x].begin();
auto [v,e2]=*next(f[x].begin());
array<int,2>e={(1ll*e1[1]*e2[0]+1ll*e1[0]*e2[1])%P,1ll*e1[1]*e2[1]%P};
if(f[u].count(v)){
f[u][v]=f[v][u]=merge(f[u][v],e);
}else{
f[u][v]=f[v][u]=e;
}
f[u].erase(x);
f[v].erase(x);
if(f[u].size()<=2){
q.push(u);
}
if(f[v].size()<=2){
q.push(v);
}
}
f[x].clear();
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
## [Luogu P10779 小 C 的独立集](https://www.luogu.com.cn/problem/P10779)
> 给定简单无向图 $G = (V, E)$，保证每条边属于且仅属于一个简单环，求 $G$ 的最大独立集大小。
其实是一个仙人掌，但同样属于广义串并联图。考虑仙人掌太难写了~~懒得学~~，因此考虑广义串并联图的方法求解。
设 $f_{e=(u,v),0/1,0/1}$ 表示边 $e=(u,v)$，$u$ 选/不选，$v$ 选/不选的对应子图的最大独立集，实际维护中需要注意 $f_{(u,v),i,j}=f_{(v,u),j,i}$。
考虑删一度点不好维护，设 $g_{x,0/1}$ 表示当前选/不选点 $x$ 且不考虑边，对于独立集的贡献。
* 删一度点，设边为 $(x,v)$，有：
$$
g_{v,i}\leftarrow g_{v,i}+\max\left(g_{x,0}+f_{(x,v),0,i},g_{x,1}+f_{(x,v),1,i}\right)
$$
* 缩二度点，设 $(x,u),(x,v)$ 缩为 $(u,v)$，有：
$$
f_{(u,v),i,j}=\max\left(f_{(x,u),0,i}+f_{(x,v),0,j}+g_{x,0},f_{(x,u),1,i}+f_{(x,v),1,j}+g_{x,1}\right)
$$
* 叠合重边，设 $e_1,e_2$ 叠合为 $e$。
这个比较简单：
$$
f_{e,i,j}=f_{e_1,i,j}+f_{e_2,i,j}
$$
初始时，由定义可知 $g_{x,0}=0,g_{x,1}=1$，$f_{e,0,0}=f_{e,0,1}=f_{e,1,0}=0,f_{e,1,1}=-\infty$。
取 $-\infty$ 可以避免转移过程中对于一条边两个端点都取的特判。
时间复杂度 $\mathcal O(n)$。
参考代码
```cpp
//#include<bits/stdc++.h>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef array<array<int,2>,2> value;
constexpr const int N=5e4,inf=0x3f3f3f3f;
int n,g[N+1][2];
unordered_map<int,value>f[N+1];
value twist(value a,value b){
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
if(a[i][j]==-inf||b[i][j]==-inf){
a[i][j]=-inf;
}else{
a[i][j]+=b[i][j];
}
}
}
return a;
}
value inv(value a){
return {a[0][0],a[1][0],a[0][1],a[1][1]};
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
while(m--){
int u,v;
cin>>u>>v;
if(f[u].count(v)){
f[v][u]=inv(f[u][v]=twist(f[u][v],{0,0,0,-inf}));
}else{
f[v][u]=inv(f[u][v]={0,0,0,-inf});
}
}
queueq;
for(int i=1;i<=n;i++){
if(f[i].size()<=2){
q.push(i);
}
g[i][1]=1;
}
int lst=0;
while(q.size()){
int x=q.front();q.pop();
if(f[x].size()==1){
auto [v,e]=*f[x].begin();
for(int i=0;i<=1;i++){
g[v][i]+=max(g[x][0]+e[0][i],g[x][1]+e[1][i]);
}
f[v].erase(x);
if(f[v].size()<=2){
q.push(v);
}
}else if(f[x].size()==2){
auto [u,e1]=*f[x].begin();
auto [v,e2]=*next(f[x].begin());
value e;
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
e[i][j]=max(e1[0][i]+e2[0][j]+g[x][0],e1[1][i]+e2[1][j]+g[x][1]);
}
}
if(f[u].count(v)){
f[v][u]=inv(f[u][v]=twist(f[u][v],e));
}else{
f[v][u]=inv(f[u][v]=e);
}
f[u].erase(x);
f[v].erase(x);
if(f[u].size()<=2){
q.push(u);
}
if(f[v].size()<=2){
q.push(v);
}
}
f[x].clear();
lst=x;
}
cout<<max(g[lst][0],g[lst][1])<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
## [Luogu P4426 [HNOI/AHOI2018] 毒瘤](https://www.luogu.com.cn/problem/P4426)
> 给定一张 $n$ 个点 $m$ 条边的图，求独立集数量（包括空集）对 $998244353$ 取模的结果。
>
> $n\leq10^5,n-1\leq m\leq n+10$。
容易发现 $m-n\leq10$，因此可以通过广义串并联图方法缩图后跑 $\mathcal O\left(2^{2k}\times3k\right)$ 的暴力。
同时类似于上一题，本题需要维护独立集的数量。
设 $f_{(u,v),0/1,0/1}$ 为边 $(u,v)$，$u$ 选/不选，$v$ 选/不选时对应子图的独立集数量；$g_{x,0/1}$ 为 $x$ 不考虑剩余边，$x$ 选/不选时对应子图的独立集数量。
* 删一度点 $x$，边为 $(x,v)$：
$$
g_{v,i}\leftarrow g_{v,i}\sum_{j=0}^1g_{x,j}\cdot f_{(x,v),j,i}
$$
* 缩二度点， $(u,x),(v,x)$ 得 $(u,v)$：
$$
f_{(u,v),i,j}=\sum_{k=0}^1f_{(x,u),k,i}\cdot f_{(x,v),k,j}\cdot g_{x,k}
$$
* 叠合重边 $e_1,e_2$ 得 $e$：
$$
f_{e,i,j}=f_{e_1,i,j}\cdot f_{e_2,i,j}
$$
缩完图后，如果原图没有边，只剩下缩完的点 $x$，则答案为 $g_{x,0}+g_{x,1}$。
否则，暴力枚举剩余每个点是否在独立集中，乘上对应的 $g_{x,i},f_{e,i,j}$，求和即可。
参考代码
```cpp
//#include<bits/stdc++.h>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef array<array<int,2>,2> value;
constexpr const int N=1e5,K=10,P=998244353,inf=0x3f3f3f3f;
int n,ans,g[N+1][2];
unordered_map<int,value>f[N+1];
value twist(value a,value b){
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
a[i][j]=1ll*a[i][j]*b[i][j]%P;
}
}
return a;
}
value inv(value a){
return {a[0][0],a[1][0],a[0][1],a[1][1]};
}
int id[K<<1|1];
bool mode[N+1];
void dfs(int p){
if(p>n){
int cnt=1;
for(int i=1;i<=n;i++){
int u=id[i];
cnt=1ll*cnt*g[u][mode[u]]%P;
for(auto [v,e]:f[u]){
if(u<=v){
cnt=1ll*cnt*e[mode[u]][mode[v]]%P;
}
}
}
ans=(ans+cnt)%P;
return;
}
mode[id[p]]=0;
dfs(p+1);
mode[id[p]]=1;
dfs(p+1);
}
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
while(m--){
int u,v;
cin>>u>>v;
if(f[u].count(v)){
f[v][u]=inv(f[u][v]=twist(f[u][v],{1,1,1,0}));
}else{
f[v][u]=inv(f[u][v]={1,1,1,0});
}
}
queueq;
for(int i=1;i<=n;i++){
if(f[i].size()<=2){
q.push(i);
}
g[i][0]=g[i][1]=1;
}
int x;
while(q.size()){
x=q.front();q.pop();
if(f[x].size()==1){
auto [v,e]=*f[x].begin();
for(int i=0;i<=1;i++){
g[v][i]=(1ll*g[x][0]*e[0][i]+1ll*g[x][1]*e[1][i])%P*g[v][i]%P;
}
f[v].erase(x);
if(f[v].size()<=2){
q.push(v);
}
}else if(f[x].size()==2){
auto [u,e1]=*f[x].begin();
auto [v,e2]=*next(f[x].begin());
value e;
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
e[i][j]=(1ll*e1[0][i]*e2[0][j]%P*g[x][0] + 1ll*e1[1][i]*e2[1][j]%P*g[x][1])%P;
}
}
if(f[u].count(v)){
f[v][u]=inv(f[u][v]=twist(f[u][v],e));
}else{
f[v][u]=inv(f[u][v]=e);
}
f[u].erase(x);
f[v].erase(x);
if(f[u].size()<=2){
q.push(u);
}
if(f[v].size()<=2){
q.push(v);
}
}
f[x].clear();
}
int cnt=0;
for(int i=1;i<=n;i++){
if(f[i].size()){
id[++cnt]=i;
}
}
n=cnt;
if(n>0){
dfs(1);
cout<<ans<<'\n';
}else{
cout<<(g[x][0]+g[x][1])%P<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
[^1]: 每条边都只在一个简单环中的图称之为仙人掌。~~多棵仙人掌构成的图称之为**沙漠**。~~
