比赛 |
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;
}