比赛 4043级NOIP2022欢乐赛6th 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 BLO-Blockade 最终得分 100
用户昵称 yrtiop 运行时间 0.547 s
代码语言 C++ 内存使用 3.88 MiB
提交时间 2022-11-18 22:09:31
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back
using i64 = long long;

const int maxn = 1e5 + 5;
const int maxm = 5e5 + 5;

int n,m,dfn[maxn],cnt,low[maxn],sz[maxn];
bool inq[maxn];
std::vector<int> G[maxn];
i64 ans[maxn];

void tarjan(int u,int fa) {
	dfn[u] = low[u] = ++ cnt;
	sz[u] = 1;
	int tot = 0,num = 0;
	for(auto& v : G[u]) {
		if(!dfn[v]) {
			tarjan(v , u);
			low[u] = std::min(low[u] , low[v]);
			sz[u] += sz[v];
			if(low[v] >= dfn[u]) {
				++ num;
				if(u != fa||num > 1)inq[u] = true;
				tot += sz[v];
				ans[u] += 1ll * (n - sz[v]) * sz[v];
			}
		}
		else low[u] = std::min(low[u] , dfn[v]);
	}
	if(!inq[u])
		ans[u] = 2 * n - 2;
	else
		ans[u] += 1ll * (n - tot - 1) * (tot + 1) + n - 1;
	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 u,v;
		scanf("%d %d",&u,&v);
		G[u].pb(v);
		G[v].pb(u);
	}
	
	tarjan(1 , 1);
	
	for(int i = 1;i <= n;++ i) {
		printf("%lld\n",ans[i]);
	}
	return 0;
}