如果节点 \(i\) 不是割点,那么只有 \(2*(n-1)\) 个点对不连通。
如果节点 \(i\) 是割点,设在搜索树上节点 \(i\) 的子节点里有 \(k\) 个节点 \(p_1,p_2,\dots,p_k\) 满足割点判断法则 \(Low[p_t] \geq Dfn[x]\) 那么这时候将节点 \(i\) 其连着的边删除后整个图分成 \(k+1\) 个联通块。
- 节点 \(i\) 单独成一个联通块。
- \(k\) 个分别由 \(p_t\) 和其分别在搜索树上的子节点组成的联通块。
- 其他所有的节点成一个联通块。
那么,这时的答案就是
\[ \sum_{i=1}^k (size(s_i)*(n-size(s_i)))+(n-1)+(n-\sum_{i=1}^ksize(s_k)-1)*(\sum_{i=1}^ksize(s_k)+1) \]
#include <iostream>
#include <cstdio>
typedef long long LL;
const int MaxN = 100000 + 5;
const int MaxM = 500000 + 5;
int N, M, Edge, Index;
int Dfn[MaxN], Low[MaxN], Size[MaxN], FST[MaxN];
bool Cut[MaxN];
LL Ans[MaxN];
struct Linker
{
int to, nxt;
Linker(){}
Linker(int u, int v)
{
to = v;
nxt = FST[u];
}
} E[MaxM << 1];
inline int read()
{
register int x = 0;
register char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
inline void AddEdge(int u, int v)
{
E[++Edge] = Linker(u, v);
FST[u] = Edge;
}
void Tarjan(int x)
{
Dfn[x] = Low[x] = ++Index;
Size[x] = 1;
int sum = 0;
bool flag;
for(int k = FST[x]; k; k = E[k].nxt)
{
int to = E[k].to;
if(!Dfn[to])
{
Tarjan(to);
Size[x] += Size[to];
Low[x] = std::min(Low[x], Low[to]);
if(Low[to] >= Dfn[x])
{
sum += Size[to];
Cut[x] = 1;
Ans[x] += 1LL * Size[to] * (N - Size[to]);
if(x != 1 || flag) Cut[x] = 1;
flag = 1;
}
}
else Low[x] = std::min(Low[x], Dfn[to]);
}
if(!Cut[x]) Ans[x] = 1LL * 2 * (N - 1);
else Ans[x] += (N - 1) + (N - sum - 1) * (sum + 1);
}
int main()
{
N = read();
M = read();
for(int i = 1; i <= M; ++i)
{
int u = read(), v = read();
if(u == v) continue;
AddEdge(u, v);
AddEdge(v, u);
}
Tarjan(1);
for(int i = 1; i <= N; ++i) printf("%lld\n", Ans[i]);
return 0;
}