LINK

使用$tarjan$求出割点,显然非割点的答案是$2\ast (n-1)$

如果是割点,割掉之后,会把原图分成若干个连通块

下面的讨论暂时不计算点$u$的贡献

考虑在$tarjan$形成的$dfs$树中

$u$的儿子分别是$v_1,v_2,v_3...$,子树大小分别是$siz[v_1],siz[v_2],siz[v_3]...$

这些儿子中，有些儿子的$low[v]>=dfn[u]$

说明这些儿子不能通过非父回边到达更浅的节点,也就是被分割为一个连通块

那么直接计算这个儿子的贡献,为$siz[v]\ast (n-1-siz[v])$

设这类儿子的总大小为$sum$,那么这些点到不了其余$(n-1-sum)$个点

加上贡献,最后加上点$u$的贡献$2\ast (n-1)$即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6+10;
int n,m,id,dfn[maxn],low[maxn],siz[maxn],ans[maxn],cut[maxn];
struct edge{
	int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){ d[++cnt] = ( edge ){v,head[u]},head[u] = cnt; }
void tarjan(int u,int fa)
{
	dfn[u] = low[u] = ++id; siz[u] = 1;
	int child = 0,sum = 0;
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		if( !dfn[v] )
		{
			child++; tarjan(v,fa);
			siz[u] += siz[v];
			if( low[v]>=dfn[u] )//发现割点 
			{
				ans[u] += siz[v]*( n-siz[v]-1 );
				sum += siz[v];
				if( u!=fa )	cut[u] = 1;
			}
			low[u] = min( low[u],low[v] );
		}
		else	low[u] = min( low[u],dfn[v] );
	}
	if( child>=2 && u==fa )	cut[u] = 1;
	if( !cut[u] )	ans[u] = 2*(n-1);
	else	ans[u] += ( n-sum-1 )*sum+2*(n-1);
}
signed main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		int l,r; cin >> l >> r;
		add(l,r); add(r,l);
	}
	tarjan(1,1);
	for(int i=1;i<=n;i++)	cout << ans[i] << endl;
}