题解

思路推导

把每条管道看成容量为 $1$ 的无向边。由最大流最小割定理，点对 $(s,t)$ 的答案等于把 $s$ 与 $t$ 分开的最小割容量，记为 $\lambda(s,t)$。

对任意源点 $s$，最大流不超过 $s$ 的度数。题目保证每个点的度数不超过 $3$，所以任意两点之间的最大流都不超过 $3$。这意味着一次最大流至多进行三次单位增广。

Gomory--Hu 树可以用 $n-1$ 次无向图最小割，把所有点对最小割压缩到一棵带权树中。树上的每条边记录一次最小割；任意两点在原图中的最小割，恰好等于它们在树上路径的最小边权。

因此问题转化为：求一棵带权树中所有点对路径最小边权之和。

做法

先构造 Gomory--Hu 树。维护每个点当前的父亲。依次选择一个点与其父亲求最大流，并从残量网络中取得源点侧的最小割集合，再按照 Gomory--Hu 算法更新尚未处理点的父亲关系和对应割值。

由于所有原边容量均为 $1$，一次增广后沿反向边增加残量容量；每次求流前把全部边恢复为初始容量。源点度数不超过 $3$，故每次最大流只有常数次广度优先搜索增广。

得到割树后，把树边按权值从大到小排序，并使用并查集合并端点。处理权值为 $w$ 的树边时，若它连接的两个并查集大小分别为 $x,y$，那么新连通的 $xy$ 对点的树上路径最小边权都等于 $w$，应把 $wxy$ 加入答案。

子任务 1 可以枚举包含其中一个端点而不包含另一个端点的所有点集，直接求每对点的最小割。子任务 2 可以对每一对点分别运行最大流。若输入图是一片森林，任意同一连通块内的不同点之间只有一条边不交路径，答案就是各连通块点数的组合数之和。

正确性证明

由最大流最小割定理，每一对节点的最大流等于它们之间的最小割容量。

Gomory--Hu 算法构造出的割树满足：任意两点 $u,v$ 在原图中的最小割容量，等于割树上 $u$ 到 $v$ 路径的最小边权。因此，只需证明并查集统计正确计算了所有树上路径最小边权之和。

按边权从大到小处理割树边。处理权值为 $w$ 的边时，它两端所在的两个并查集内部都只通过权值不小于 $w$ 的边连接，而这两个集合此前尚未连通。此时跨越两个集合的任意点对，其路径必经当前边，且路径上的其他已处理边权均不小于 $w$，所以路径最小边权恰为 $w$。这样的点对共有 $xy$ 对，贡献为 $wxy$。每一对点恰好在它们第一次被合并到同一集合时统计一次，故总和正确。

综上，算法输出所有点对最大流之和。

复杂度分析

每次最大流至多进行三次单位增广，耗时 $O(n+m)$。Gomory--Hu 树需要 $n-1$ 次最大流，总时间复杂度为 $O(n(n+m))$；割树排序耗时 $O(n\log n)$。空间复杂度为 $O(n+m)$。