【bzoj1123】BLO

  • 本文为博主原创,未经许可不得转载

求出割点,然后统计答案即可

做水题的感觉挺爽的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100010
#define MAXM 500010
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
typedef long long ll;
struct node{int y,next;}e[MAXM<<1];
int n,m,len,dfs_clock,Link[MAXN],dfn[MAXN],low[MAXN],size[MAXN]; ll ans[MAXN];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
int x=0,f=1; char ch=getc();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
return x*f;
}
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
void tarjan(int x){
dfn[x]=low[x]=++dfs_clock; size[x]=1; int sum=0;
for(int i=Link[x];i;i=e[i].next){
if(!dfn[e[i].y]){
tarjan(e[i].y); cmin(low[x],low[e[i].y]);
size[x]+=size[e[i].y];
if(low[e[i].y]>=dfn[x]){
ans[x]+=(ll)size[e[i].y]*sum*2;
sum+=size[e[i].y];
}
}
else cmin(low[x],dfn[e[i].y]);
}
ans[x]+=(ll)sum*(n-sum-1)*2+(n-1)*2;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read(); m=read();
for(int i=1;i<=m;++i){
int x=read(),y=read();
insert(x,y); insert(y,x);
}
tarjan(1);
for(int i=1;i<=n;++i) printf("%lld\n",ans[i]);
return 0;
}
文章目录
,