广义串并联图

Iruka_Okazaki · 2025-08-18 12:44:49 · 算法·理论

\text{Part 0}

以防自己学了又忘，所以开个坑。

这种板板的东西要是在考场上遇到了但是想不起来还是十分可惜的。

\text{Part 1}

广义串并联图指一类不存在同胚于 K_4 的子图的图，即不存在四个点 a,b,c,d 使得这四个点之间存在六条除顶点外不相交的路径连接每一对点。而广义串并联图经过以下的操作后可以变为一个点：

删一度点：选择一个度数为 1 的点并删掉它和与它连接的边。
缩二度点：选择一个度数为 2 的点，用一条边替换它和与它相连的两条边。
叠重边：选择两条重边，用一条边替换它们。

我们称以上的方法为广义串并联图方法。广义串并联图在正常的题目中十分罕见，所以我们一般使用的都是广义串并联图方法。当我们在见到 m \le n + k 的时候，我们会考虑使用广义串并联图方法。

Lemma:

任意一张图在经过广义串并联图方法后的点数在 \mathrm O(k) 级别。

Proof:

做完以上的操作之后，我们知道一定只剩度数 \ge 3 的点了，所以 3n \le 2m。那么我们就有 n \le 2k,m \le 3k。所以我们在操作完之后的点就在 \mathrm O(k) 级别的了。

考虑怎么去做哪些操作。我们可以考虑用 map 维护所有的边，然后用队列维护度数 \le 2 的点，然后重复操作即可。

\text{Part 2}

定义一张广义串并联图的串并联树为：

删 1 度点操作：将被删除点 x，与其相连的边 a 和 a 的另一个端点 z 对应的树上节点 v_x,v_a,v_z 的父亲设为 v^{\prime}，然后将点 z 对应的树上节点设为 v^{\prime}。
缩 2 度点操作：将被删除点 x 和与其相连的两条边 a,b 对应的树上节点 v_x,v_a,v_b 的父亲设为 v^{\prime}，然后将建立的新边对应的树上节点设为 v^{\prime}。
叠重边操作：将两条重边 a,b 对应的树上节点 v_a,v_b 的父亲设为 v^{\prime}，然后将合并后的边对应的树上节点设为

串并联树有以下的性质：

每一个树上节点唯一对应图上的一个点或一条边，初始图 G 中每一个点或一条边唯一对应一个树上叶子节点。
每一个非叶子节点也对应一个收缩操作。
串并联树是一棵三叉树。

注意，你只有在广义串并联图上才建得出来串并联树。

定义串并联树上节点 u 的内部图 G^{\prime}_u 为初始图 G 的一个子图。

如果点 u 在图上对应的是一个点，那么对于初始图 G，如果图上的一个点或一条边对应的树上叶子节点在点 u 的子树中，那么这个点或边属于 G_u^{\prime}。
如果点 u 在图上对应的是一条边，设这条边为 (x,y)，那么对于初始图 G，如果图上的一个点或一条边对应的树上叶子节点在点 u 的子树中，那么这个点或边属于 G^{\prime}_u，且点 x 和点 y 也属于 G^{\prime}_u。

同时定义外部图为先进行所有在点 u 子树内的收缩操作后的图。此时称分割点为内部图和外部图的交集，当树上的节点 u 在原图中表示的是一个节点，则只有一个分割点。如果为一条边，则有两个分割点。

\text{Part 3}

\text{Example 0}

基础练习题。请读者自行完成。

code。

\text{Example 1}

直接猜测这个图是一个广义串并联图，所以考虑用广义串并联图方法。

对于每一条边我们考虑维护 (f,g) 表示这条边在不在生成树上，此时考虑三种操作之后的图长什么样子：

删一度点：将这条边的 f 乘进答案即可。
缩二度点：由于这两条边必须有一条在生成树上，同时缩出来的边只有当两条边都存在时才存在，所以我们有：

\begin{cases}f_e=f_{e_1}f_{e_2}\\g_e=f_{e_1}g_{e_2}+f_{e_2}g_{e_1}\end{cases}

叠重边：这两条边不能同时在生成树上，同时，只有两条边都不存在这条边才不存在，所以我们有：

\begin{cases}f_e=f_{e_1}g_{e_2}+f_{e_2}g_{e_1}\\g_e=g_{e_1}g_{e_2}\end{cases}

由于他是一个广义串并联图所以在完之后我们不需要处理。

\text{Example 2}

注意到有一个部分分是 m \le n + 13，那么考虑广义串并联图。

先求出 1 \to n 的最短路 L。然后每一次操作的时候维护时维护一下新边的最长距离，具体的：

删一度点：由于不能走回头路，所以这个点没有用。
缩二度点：新边的权值为原来两边之和。
叠重边：新边的边权为原本两边的 \max。

但是注意我们不能把 1,n 这两个点删了。在删完点之后，我们发现我们剩下的图么是要么是一条连接 1 和 n 的边，要么是剩下一个每个点度数不小于 3 的图。

注意后面的情况，在 1 \to n 的若干条路径上，路径上的每个点都至少连出一条横插边，容易发现这样是不能使得所有路径的长度相同的，所以答案是 Yes。

\text{Example 3}

建出串并联树。

对于一个表示边的叶子结点，我们用一个向量 (w_{0,0},w_{0,1},w_{1,0},w_{1,1}) 来描述他，表示左右两边的点分别为黑白状态的权值。

对于一个表节点的叶子结点，我们用一个向量 (b,w) 来表述它，分别表示这个点分别为黑或白状态的权值。

考虑在进行一下的操作会给边权带来什么样的变化：

删一度点：对于一个叶子节点 v，设其父亲节点为 u。
1. 假如节点 u 为白色那么 v 能带来的贡献即为 \max(w_{(u,v),1,1} + w_v,w_{(u,v),1,0} + b_v)。
2. 假如节点 u 为黑色那么 v 能带来的贡献即为 \max(w_{(u,v),0,0} + b_v,w_{(u,v),0,1} + w_v)。
缩二度点：对于一个点 x，其出度为 2，且两条边分别为 (x,u),(x,v)，则我们有：
1. w_{0,0} = \max(w_{(u,x),0,0} + b_x + w_{(x,v),0,0}, w_{(u,x),0,1} + w_x + w_{(x,v),1,0})
2. w_{0,1} = \max(w_{(u,x),0,0} + b_x + w_{(x,v),0,1}, w_{(u,x),0,1} + w_x + w_{(x,v),1,1})
3. w_{1,0} = \max(w_{(u,x),1,0} + b_x + w_{(x,v),0,0}, w_{(u,x),1,1} + w_x + w_{(x,v),1,0})
4. w_{1,1} = \max(w_{(u,x),1,0} + b_x + w_{(x,v),0,1}, w_{(u,x),1,1} + w_x + w_{(x,v),1,1})
叠重边：直接相加即可。但需要注意的是 (u,v) 是有序的。所以假如另一条边为 (v,u)，那么需要现将其反转。

如果没有修改的话那么直接在串并联树上直接查，如果有修改那么对于串并联树进行动态 dp 即可。

\text{Example 4}

注意到题目保证了他是一个广义串并联图，那直接建出其串并联树。

考虑使用树分治，假设现在的分治重心为 u，那么设 u 的分割点为 p_1,p_2（p_2 可能不存在）。然后统计所有询问中所有满足 x 属于内部图且 y 属于外部图的点对 (x,y) 的贡献。

由于 x,y 的路径一定会经过 p_1 或者 p_2，那么我们就可以知道其最短路长度为：

dis_{(x,y)} = \min \{dis_{x,p_1} + dis_{y,p_1},dis_{x,p_2} + dis_{y,p_2}\}

此时注意到答案取那一边和 (dis_{x,p_1} - dis_{x,p_2}) + (dis_{y,p_1} - dis_{y,p_2}) 有关。所以可以考虑将图中所有的点按照其到 p_1,p_2 的距离之差从小到大排序。在统计完答案之后，如果我们有两个分割点，我们需要加上 dis_{p_1,p_2}。然后再将内部图和外部图拆开，然后继续递归。

复杂度 \mathrm O((n + K) \log^2 n)。

\text{Part 4}

总结一下，当我们见到 m \le n + k 且 k 较小的时候，可以考虑使用广义串并联图方法来简化这张图。

如果题目给定了一张广义串并联图，则可以考虑建出一颗串并联树然后再树上进行一些操作。