自以为与题解相差无几,可还是挂了
查看原帖
自以为与题解相差无几,可还是挂了
713826
EDJIW楼主2025/6/17 20:43

RT,参考第一篇题解

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=5e5+50;
ll n,m,cnt,idx;
ll dfn[N],low[N],st[N],tp,num[N],tot,ans,siz[N];
struct Node{
	ll to[N*2],nex[N*2],la[N],mcnt=1;
	void add(ll u,ll v){
		mcnt++;
		nex[mcnt]=la[u],to[mcnt]=v;
		la[u]=mcnt;
	}
}a,b;

void tarjan(ll x,ll lst){
	dfn[x]=low[x]=++cnt;
	num[x]=-1;
	st[++tp]=x;
	tot++;
	for(ll i=a.la[x];i;i=a.nex[i]){
		if(lst==(i^1))continue;
		ll to=a.to[i];
		if(!dfn[to]){
			tarjan(to,i);
			low[x]=min(low[x],low[to]);
			if(dfn[x]<=low[to]){
				ll v;idx++;num[idx]++;
				b.add(idx,x);b.add(x,idx);
				do v=st[tp--],num[idx]++,b.add(idx,to),b.add(to,idx);while(v!=to);
			}
		}
		else low[x]=min(low[x],dfn[to]);
	}
}

void dfs(ll x,ll fa){
	siz[x]=x<=n;
	for(ll i=b.la[x];i;i=b.nex[i]){
		ll to=b.to[i];
		if(to==fa)continue;
		dfs(to,x);
		ans+=2ll*siz[x]*siz[to]*num[x];
		siz[x]+=siz[to];
	}
	ans+=2ll*siz[x]*(tot-siz[x])*num[x];
}

int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1,u,v;i<=m;i++){
		scanf("%lld%lld",&u,&v);
		a.add(u,v);a.add(v,u);
	}
	idx=n;
	
	for(ll i=1;i<=n;i++){
		if(!dfn[i]){
			tot=tp=0;
			tarjan(i,-1);
			dfs(i,0);
		}
	}
	
	printf("%lld",ans);
	
	return 0;
} 
2025/6/17 20:43
加载中...