C++14(g++5.4) 解法, 执行用时: 591ms, 内存消耗: 27608K, 提交时间: 2020-01-16 12:25:40

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=5e5+20;
ll n,m,cnt;
ll dfn[MX],low[MX];
ll ans_option[MX],num[MX];
vector<int>ve[MX];
bool vis[MX];
void tarjan(int now)
{
	dfn[now]=low[now]=++cnt;
	num[now]=1;
	int flag=0;
	ll sum=0;
	for(int v:ve[now])
	{
		if(!dfn[v])
		{
			tarjan(v);
			num[now]+=num[v];
			low[now]=min(low[v],low[now]);
			if(low[v]>=dfn[now])
			{
				ans_option[now]+=(n-num[v])*num[v];
				sum+=num[v];
				flag++;
				if(now!=1||flag>1) vis[now]=1;
			}
		}
		else low[now]=min(low[now],dfn[v]);
	}
	if(!vis[now]) ans_option[now]=(n-1)*2;
	else ans_option[now]+=(n-sum-1)*(sum+1)+(n-1);
}
int main()
{
	cin>>n>>m;
	for(int i=0,x,y;i<m;i++)
	{
		cin>>x>>y;
		ve[x].push_back(y);
		ve[y].push_back(x);
	}
	tarjan(1);
	for(int i=1;i<=n;i++)
	{
		cout<<ans_option[i]<<'\n';
	}
	return 0;
}
/*
5 5
1 2
2 3
1 3
3 4
4 5
*/

C++(clang++11) 解法, 执行用时: 240ms, 内存消耗: 15860K, 提交时间: 2020-10-25 20:52:41

#include<bits/stdc++.h>
#define eb emplace_back
#define ui unsigned int
using namespace std;
const ui nn=101023;
bool in[nn],cut[nn];
ui n,m,f[nn],dfn[nn],size[nn];
long long ans[nn];
vector<ui>to[nn];
ui dfs(ui u,ui f){
	ui s,lu,lv;
	in[u]=true,size[u]=s=1,lu=dfn[u]=++dfn[0];
	for(ui i=0,v;i<to[u].size();i++){
		v=to[u][i];
		if(dfn[v]){
			if(in[v]&&v!=f)lu=min(lu,dfn[v]);
		}else{
			lu=min(lu,lv=dfs(v,u)),size[u]+=size[v];
			if(dfn[u]<=lv)ans[u]+=1ll*s*size[v],s+=size[v];
		}
	}ans[u]+=1ll*s*(n-s),in[u]=false;
	return lu;
}int main(){
	scanf("%u%u",&n,&m);
	for(ui a,b;m--;)
		scanf("%u%u",&a,&b),
		to[a].eb(b),to[b].eb(a);
	dfs(1,0);
	for(ui i=1;i<=n;i++)
		printf("%lld\n",ans[i]<<1);
	return 0;
}