广义串并联图_成型笔记

广义串并联图

我觉得一个 $\text{noip}$ 二等人来学这个就是玩原神玩的。

本来一直念叨着想学，然后前两天：

---

下面的讨论均基于无向连通图。

形式化标准定义：不存在与 $\mathbb K_4$ 同胚的子图的图（没什么用）。

$\mathbb K_4$：含有 $4$ 个点的完全图。

子图：$(V,E)$ 的子图 $(V',E')$ 满足 $V'\sube V,E'\sube E,(\forall x,y\in V',(x,y)\in E),(x,y)\in E'$。

同构：存在一种重排点序号和边序号的方式使得两个图的边集数组完全相同。

同胚：将链状结构看作一条边后同构。

性质：

• 平面图。
• 可以通过删一度点、缩二度点、叠合重边来将该图收缩为一个单点。
• 去除重边后 $m\le 2n$。

直观理解广义串并联图就是可以通过删一度点、缩二度点、叠合重边将图收缩为单点的图。

（图名的来源可能就是缩二度点类似于“串联”，叠合重边类似于“并联”。）

如果你不理解那三个名词的话：

用途的话，可能算挺有用的？

对一个 $|E|-|V|=k$ 的一般图来说，有定理为将其尽可能删一度点、缩二度点、叠合重边之后形成的图 $|V'|\le 2k,|E'|\le 3k$。

$\text{Proof}$：

缩二度点和叠合重边会导致 $|E|-|V|$ 减少 $1$，删一度点会导致 $|E|-|V|$ 不变。

而最终的图一定是一个丑陋的所有点度数 $\ge 3$，即 $2|E|\ge 3|V|$，又有 $|E|\le |V|+k$，所以 $|V|\le 2k,|E|\le 3k$。

所以如果题目有某种 $m-n\le 10$ 类似的条件，那大概率是一道广义串并联图题。

下文为了方便，称这个无法继续化简的图为终图，将删一度点、缩二度点、叠合重边称作删点、串联、并联。

代码模板

广义串并联图通常要对一条边设置某种类似于权值的东西，所以一般的写法会记录边的权值，由于我们的边变动较多，常使用可加边删边的 std::map 或 std::set，以及它们的哈希形式。

先来个朴素写法，如果你只是想要将一张图缩成终图，你可以较为方便地使用 std::set 写法（换成 std::unordered_set 可以少一个 $\log$。）

其中 std::set 中存储的是每个点的出点们。

#define d(x) int(v[x].size())
#define T(x) if(d(x)<=2) q.push(x)
set<int> v[N];queue<int> q;
void add(int x,int y) {v[x].ins(y);v[y].ins(x);}
void fit() {
    F(x,1,n) T(x);
    while(!q.empty()) {
        int x=q.front();q.pop();
        if(!d(x)) continue;
        if(d(x)==1) {
            int y=*begin(v[x]);
            v[x].clear();v[y].erase(x);
            T(y);
        } else {
            int y=*begin(v[x]),z=*rbegin(v[x]);
            v[x].clear();v[y].erase(x);v[z].erase(x);
            add(y,z);T(y);T(z);
        }
    }
}

如果你确实是想要往边上记录一些信息（事实上我们通常这样做），你可以使用如下模板（std::map 的键值对分别表示出点和边编号，换成 std::unordered_map 可以少一个 $\log$。）：

#define d(x) int(G[x].size())
#define fi first
#define se second
#define T(x) if(d(x)<=2) q.push(x)
using pii=pair<int,int>;
map<int,int> G[N];queue<int> q;
void r1(int i) {}//merge info of i to answer 删一度点
void r2(int i,int j) {}//add info of j to i 缩二度点
void rr(int i,int j) {}//add info of j to i 叠合重边
void add(int x,int y,int i) {if(G[x][y]) rr(i,G[x][y]);G[x][y]=G[y][x]=i;}
void fit() {queue<int> q;
    F(x,1,n) T(x);
    while(!q.empty()) {
        int x=q.front();q.pop();
        if(!d(x)) continue;
        if(d(x)==1) {
            auto[y,i]=*begin(v[x]);
            G[x].clear();G[y].erase(x);
            r1(i);T(y);
        } else {
            auto[y,i]=*begin(G[x]);
            auto[z,j]=*++begin(G[x]);
            G[x]={};G[y].erase(x);G[z].erase(x);
            r2(i,j);add(y,z,i);T(y);T(z);
        } 
    }
}

刚刚在想缩二度点是不是还得分为两点已连接和两点未连接，后来想到两点已连接那不就是叠合重边嘛。

每次整理算法模板的时候总可以从参考对象那里进行大量的简化，看来大家写代码都是比较随心的。

$\text{WARNING}$：本代码适用于如果删到 $\text{deg}=0$ 的点不需要特殊处理的情况，由于本代码可能造成一个点多次入队，请谨慎判断是否有特殊情况再使用。

例题

看了上面的部分你发现这个东西好像很简单。

那就来看看下面的例题吧。

练习这个东西之前一直以为是先发现原问题等价于缩完之后的图，然后爆搜解决。

但实际上广义串并联图的应用通常是与式子的转化有关。

先来道小例题来体会一下我到底在说什么：

P6790 [SNOI2020] 生成树

给定一个无向联通图，保证存在一条边，使得删去它原图成为一个边仙人掌，求该图的生成树个数。

$n\le 2\times10^5$。

首先你要猜这是一个广义串并联图，然后你就可以不用管原题到底给了什么图条件了。

$\text{Proof}$：

事实上人类智慧是可以感受出来的，一个仙人掌添加一条边显然不能构成与 $\mathbb K_4$ 同胚的子图，至少也要添加两条边（类似于在一个环中画一个“$\times$”）。

然后那广义串并联图咋做呢？

对每条边设置权值 $(f,g)$，表示将缩到这个边里面的东西视作一整条边，选/不选该边的方案数。

初始 $(f,g)=(1,1)$。

然后构造转移：

• 删点：该边必选，$ans'\gets f_i*ans$。
• 串联：选该边相当于全联通，都要选，不选该边也要保证中间的那个点被连上：$(f,g)\gets(f_if_j,f_ig_j+g_if_j)$。
• 并联：选该边选恰好一条即可，不选该边就是都不选：$(f,g)\gets(f_ig_j+g_if_j,g_ig_j)$。

就完了，黑题就这么做完了。

代码。

寒冬

给定一个无向连通图，保证 $m-n=5$，共有 $k$ 种颜色，求染色方案数。

$n\le 10^5,k\le 10^9$。

首先因为这是一篇广义串并联图笔记，所以要用缩图。

然后就是喜闻乐见的设状态串并联：$(f,g)$ 表示每条边的两个点同色/不同色的方案数（这里状态中认为颜色是无序的）。

注意每条边其实代表了缩完之后的一坨东西，所以这两个点其实是有可能同色的。

推转移的时候如何判别添加的这个系数是多余的还是需要的，由于我们规定了在场上的点颜色的无序性或者说待枚举性，所以我们仅对消失的点枚举其颜色数贡献到权值或答案中。

初始 $(f,g)=(0,0)$。

• 删点：同色的话就直接绑定颜色，异色的话就可以选 $k-1$ 种，$ans'\gets ans*(f+(k-1)g)$。
• 串联：
  • 同色情况包括三点同色 $f_1f_2$，两端点都跟被删点不同色，则被删点有 $k-1$ 种合法情况，$(k-1)g_1g_2$；
  • 异色情况包括一点跟被删点同色一点不同色 $f_1g_2+g_1f_2$，两点都跟被删点不同色且这两点不同色，则被删点有 $k-2$ 种合法情况 $(k-2)g_1g_2$；
  • $(f,g)\gets(f_1f_2+(k-1)g_1g_2,f_1g_2+g_1f_2+(k-2)g_1g_2)$。
• 并联：各情况都需满足，直接相乘即可，$(f,g)\gets(f_1f_2,g_1g_2)$。

先别急，这个题缩完了之后并不是单点。

所以还要再来一步暴力：$f_{i,S}$ 表示 $S$ 集合中的点已经用了 $i$ 种颜色的方案数，转移就是枚举新颜色是什么集合，然后 $\Theta(m'+n')$ 利用已知信息来计算方案数。

最后统计答案就是：

$$\sum_i\binom k if_{i,U}$$

设 $k=m-n$，则复杂度为 $\Theta(3^{2k}k+m)$。

我不知道为什么我脑子抽了最后一个小状压想了这么久。

代码。

需要注意的一点是，缩完后的问题绝大多数情况下可以通过子集卷积来实现 $\Theta(3^n)\to\Theta(2^n)$。