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