题目回顾

给定一个 $n$ 个点 $m$ 条边的无向图，求有多少点对 $(u,v)$ $(u \neq v)$ 满足：从 $u$ 到 $v$ 的所有简单路径上的点构成的导出子图是一个以 $u,v$ 为端点的二端串并联图。

二端串并联图的定义：

由两个点一条边的二端图经过一系列串联、并联操作形成

串联：将图 $X$ 的汇点与图 $Y$ 的源点合并

并联：将图 $X$ 和 $Y$ 的源点合并，汇点合并

算法思路

本题采用 点双连通分量分解 + 树型 DP 的方法。

1. 点双连通分量分解

使用 Tarjan 算法 求出所有点双连通分量（BCC）。 对于每个点双，我们单独处理它内部的串并联结构。

关键性质：一个图是二端串并联图当且仅当它是平面图且边数 $m = 2n - 2$（即每个点双都是多边形或多个多边形并联）。

2. 串并联归约

在每个点双内，我们模拟电阻网络的串并联化简过程：

维护一个图，初始时每条边是一个二端组件（typ=1）

不断进行两种操作：

串联：如果两个组件共享一个度数为 $2$ 的点，合并它们

并联：如果两个组件端点相同，合并它们

代码中的数据结构：

head[k], tail[k]：组件 $k$ 的子组件链表

typ[k]：组件类型（$1$ 为并联，$2$ 为串联）

px[k], py[k]：组件的两个端点

3. 树型统计

在归约后的组件树上进行 DFS 统计：

对于并联组件（typ=1）： 如果有 $c$ 个串联子组件，那么会形成 $c-1$ 个额外的并联结构

贡献为：$res \leftarrow res - (c-1) \times f_{px} \times f_{py}$

其中 $f_u$ 表示以 $u$ 为根的子树大小

对于串联组件（typ=2）： 收集所有端点，计算两两点对的贡献

贡献为：$res \leftarrow res + \sum_{i<j} f_{x_i} \times f_{x_j}$

4. 状态转移

处理完一个点双后，更新根节点的 $f$ 值：

$f_{rt} \leftarrow f_{rt} + \sum_{v \in \text{BCC}, v \neq rt} f_v$

复杂度分析

时间复杂度：$O(n + m)$

Tarjan 算法 $O(n + m)$，每个点双内的归约操作总数 $O(n + m)$

空间复杂度：$O(n + m)$

总结

本题的难点在于：

1.理解二端串并联图的组合结构

2.将图论问题转化为点双连通分量上的树型 DP

3.设计合适的组件归约算法

通过点双分解和串并联归约，我们能够高效地统计所有满足条件的点对，避免了暴力枚举的高复杂度。