自己写的一直30分,同学帮我把计算答案的那部分改到tarjan里就A了,蒟蒻想请教一下为什么
改之前
void tarjan(int x){
dfn[x]=low[x]=++nw;
int ch=0;
for(int i=head[x];i!=0;i=e[i].nxt){
int to=e[i].to;
if(!dfn[to]){
tarjan(to);
low[x]=min(low[x],low[to]);
ch++;
if(ch>1&&x==1) vis[x]=true;
else if(x!=1&&dfn[x]<=low[to]) vis[x]=true;
}
else low[x]=min(low[x],dfn[to]);
}
}
void calc(int x){
if(!vis[x]){
ans[x]=2*(n-1);
}
siz[x]=1;
v[x]=true;
for(int i=head[x];i!=0;i=e[i].nxt){
int to=e[i].to;
if(v[to]) continue;
v[to]=true;
calc(to);
siz[x]+=siz[to];
if(vis[x]){
ans[x]+=siz[to]*(n-siz[to]-1);
//cout<<"qaq "<<ans[x]<<endl;
}
}
if(vis[x]){
ans[x]+=(n-siz[x])*(siz[x]-1);
ans[x]+=2*(n-1);
}
}
改之后
void tarjan(int x){
dfn[x]=low[x]=++nw;
int ch=0, sum = 0;
siz[x]=1;
for(int i=head[x];i!=0;i=e[i].nxt){
int to=e[i].to;
if(!dfn[to]){
tarjan(to);
low[x]=min(low[x],low[to]);
ch++;
siz[x]+=siz[to];
if(dfn[x]<=low[to]) {
vis[x]=true;
sum+=siz[to];
ans[x]+=siz[to]*(n-siz[to]);
}
if(vis[x]){
//cout<<"qaq "<<ans[x]<<endl;
}
}
else low[x]=min(low[x],dfn[to]);
}
if(vis[x]){
ans[x]+=(n-sum-1)*(sum+1);
ans[x]+=(n-1);
}
else ans[x]=(n-1)*2;
}