比赛 4043级NOIP2022欢乐赛6th 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 BLO-Blockade 最终得分 100
用户昵称 op_组撒头屯 运行时间 0.466 s
代码语言 C++ 内存使用 8.45 MiB
提交时间 2022-11-18 20:38:56
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000+5;
const int M=500000+5;
struct sdf{
	int to,next;
}eg[2*M],eg2[4*N];
int head[N],ne=0;
int head2[2*N],ne2=0;
int n,m;
void add(int x,int y){
	eg[++ne]={y,head[x]};
	head[x]=ne;return ;
}
void add2(int x,int y){
	eg2[++ne2]={y,head2[x]};
	head2[x]=ne2;return ;
}
int dfn[N],low[N],tim=0;
int st[N],tp=0;
bool isge[N]={0};
vector<int>dcc[N];
int cnt=0,id[N];
void dfs(int pt){
	dfn[pt]=low[pt]=++tim;
	st[++tp]=pt;
	int tg=0;
	for (int i=head[pt];i!=0;i=eg[i].next){
		int v=eg[i].to;
		if (!dfn[v]){
			dfs(v);
			low[pt]=min(low[pt],low[v]);
			if (dfn[pt]<=low[v]){
				tg++;
				if (pt!=1||tg>1)isge[pt]=1;
				int now;cnt++;
				dcc[cnt].push_back(pt);
				do{
					now=st[tp--];
					dcc[cnt].push_back(now);
				}while(now!=v);
				
			}
		}
		else low[pt]=min(low[pt],dfn[v]);
	}
	return ;
}
int nwpt[N],tot=0;
int sz[2*N]={0};
ll ans[2*N];
void dp(int pt,int fa){
	ll s1=0,s2=0;
	if (pt<=cnt)sz[pt]=dcc[pt].size();
	else sz[pt]=1;
	for (int i=head2[pt];i!=0;i=eg2[i].next){
		int v=eg2[i].to;
		if (v==fa)continue;
		dp(v,pt);
		sz[pt]+=sz[v]-1;
		s1+=sz[v]-1;
		s2+=1ll*(sz[v]-1)*(sz[v]-1);
	}
	if (pt>cnt){
		s1+=n-sz[pt];
		s2+=1ll*(n-sz[pt])*(n-sz[pt]);
		ans[pt]=s1*s1-s2;
	}
	return ;
}
int main(){
	freopen ("BLO.in","r",stdin);
	freopen ("BLO.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1);
	tot=cnt;
	for (int i=1;i<=n;i++){
		if (isge[i])nwpt[i]=++tot;
	}
	for (int i=1;i<=cnt;i++){
		for (int j=0;j<dcc[i].size();j++){
			int x=dcc[i][j];
			if (isge[x]){
				add2(nwpt[x],i);add2(i,nwpt[x]);
			}
			else id[x]=i;
		}
	}
	dp(1,0);
	for (int i=1;i<=n;i++){
		if (!isge[i])printf("%d\n",2*(n-1));
		else printf("%lld\n",ans[nwpt[i]]+2*(n-1));
	}
	return 0;
}