题目
点这里看题目。
分析
首先，我们很容易看出，在 \(s\) 和 \(f\) 确定时，\(c\) 的备选数量就等于\(s\)到\(f\)所有简单路径的并的大小减二（要把\(s\)和\(f\)去掉）。
随手画几个图就会发现， \(s\) 到 \(f\) 所有简单路径的并似乎也就是\(s\)到\(f\)经过的所有点双的并。
考虑证明这个猜想。首先，由于点双之间最多只有一个公共点，所以每个点双内，每条从 \(s\) 到 \(f\) 的简单路径，必然是从一个固定点进入点双，从另一个固定点离开。
因而我们只需要再证明：在点双内部，对于任意三点\(a, b, c\)，必然存在简单路径满足从\(a\)到\(c\)到\(b\)。
为了方便，以下用\(u\overset{c}{\rightarrow}v\)表示从\(u\)向\(v\)连一条容量为\(c\)的边。
考虑构建一个网络来证明，如下：
-
拆点。对于\(u\)拆成\(u\)和\(u‘\)，并且连接\(u\overset{1}{\rightarrow} u‘\)，表示每个点只能经过一次。
-
拆边。无向边先要拆成有向边。对于有向边\((u,v)\)，连接\(u‘\overset{1}{\rightarrow} v\)，表示边只能经过一次。
-
连接源汇。连接\(S\overset{2}{\rightarrow} c, a‘\overset{1}{\rightarrow} T,b‘\overset{1}{\rightarrow} T\)。
这样，如果原图最大流为 \(2\) ，则存在需要的路径。
也就是说，我们需要证明，原图最大流，也即是最小割为 \(2\) 。
设最小割为\(C\)。显然\(C\le 2\)。那么我们需要证明\(C>1\)，即不可以只删除一条边就使得\(S\)到\(T\)不连通。
分类讨论：
-
如果删除 \(u\overset{1}{\rightarrow} u‘\) 的边，我们就相当于拆掉了一个点。根据点双的定义，不影响连通性。
-
如果删除 \(u‘\overset{1}{\rightarrow} v\) 的边，我们就相当于拆掉了一条边。由于这个操作影响比拆点更小，因而也不影响连通性。
-
删除\(a‘\overset{1}{\rightarrow} T\)或者是\(b‘\overset{1}{\rightarrow} T\)。显然只删除一边而另一边留存都不会影响连通性。
因而有\(C>1\)，根据连边特性我们知道就有\(C=2\)，即命题成立。
这也就是说，我们的猜想也是成立的。
因而我们只需要统计任意两点之间，经过的点双的并的大小减二即可。
考虑建出圆方树，这样任意两点之间经过的点双就是路径上的方点。
下面需要使用到一个技巧：为圆方树上的点赋合适的权。
这一题中，我们首先可以猜想给方点赋为点双大小。由于两个点双之间最多只有一个交点，因而我们可以直接给圆点赋为 \(-1\) 进行扣除多余贡献。同时，圆点赋 \(-1\) 也能顺带处理 " 并集大小减二 " 这个情况。
总结一下，我们给圆点赋 \(-1\) ，方点赋大小，然后统计任意两个圆点之间路径的权值和即可。建出圆方树后一边 DFS 计算答案即可。时间\(O(n)\)。
代码
#include <cstdio>
typedef long long LL;
const int MAXN = 2e5 + 5, MAXM = 2e6 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > ‘9‘ || s < ‘0‘ ){if( s == ‘-‘ ) f = -1; s = getchar();}
while( s >= ‘0‘ && s <= ‘9‘ ){x = ( x << 3 ) + ( x << 1 ) + ( s - ‘0‘ ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( ‘-‘ ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + ‘0‘ );
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
struct GRAPH
{
struct edge
{
int to, nxt;
}Graph[MAXM << 1];
int head[MAXN] = {}, cnt;
GRAPH() { cnt = 0; }
void addEdge( const int from, const int to )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
head[from] = cnt;
}
void addE( const int from, const int to )
{
addEdge( from, to ), addEdge( to, from );
}
void nxt( int &ptr ) const { ptr = Graph[ptr].nxt; }
edge& operator [] ( const int indx ) { return Graph[indx]; }
}G, T;
int stk[MAXN];
int siz[MAXN], w[MAXN];
int DFN[MAXN], LOW[MAXN];
LL ans;
int N, M, cnt, ID, top, tot, subn;
void Tarjan( const int u, const int fa )
{
subn ++;
DFN[u] = LOW[u] = ++ ID;
w[stk[++ top] = u] = -1;
for( int i = G.head[u], v ; i ; G.nxt( i ) )
if( ( v = G[i].to ) ^ fa )
{
if( ! DFN[v] )
{
Tarjan( v, u );
LOW[u] = MIN( LOW[u], LOW[v] );
if( LOW[v] >= DFN[u] )
{
T.addE( ++ tot, u ), w[tot] ++;
do T.addE( tot, stk[top] ), w[tot] ++;
while( stk[top --] ^ v );
}
}
else LOW[u] = MIN( LOW[u], DFN[v] );
}
}
void DFS( const int u, const int fa )
{
siz[u] = u <= N;
for( int i = T.head[u], v ; i ; T.nxt( i ) )
if( ( v = T[i].to ) ^ fa )
{
DFS( v, u );
ans += 2ll * siz[u] * siz[v] * w[u];
siz[u] += siz[v];
}
ans += 2ll * siz[u] * ( subn - siz[u] ) * w[u];
}
int main()
{
read( N ), read( M ), tot = N;
for( int i = 1, a, b ; i <= M ; i ++ )
read( a ), read( b ), G.addE( a, b );
for( int i = 1 ; i <= N ; i ++ )
if( ! DFN[i] )
{
subn = 0;
Tarjan( i, 0 );
DFS( i, 0 );
}
write( ans ), putchar( ‘\n‘ );
return 0;
}