82pts,求调!
查看原帖
82pts,求调!
907430
corner_xiejunqi楼主2025/7/24 17:43

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;
int n,m;
vector<int> g[N];
map<int,int> cut;
int dfn[N],low[N],cnt;
ll ans[N],size[N];
inline void dfs(int now,int fa){
	dfn[now]=low[now]=++cnt;
	size[now]=1;
	ll ch=0,sum=0;
	for(auto to:g[now]){
		if(to==fa) continue;
		if(dfn[to]) low[now]=min(low[now],dfn[to]);
		else{
			dfs(to,now);++ch;
			size[now]+=size[to];
			low[now]=min(low[now],low[to]);
			if(fa!=0 && low[to]>=dfn[now]){
				cut[now]=1;
				ans[now]+=(ll)size[to]*(n-size[to]);
				sum+=(ll)size[to];
			} 
		}
	}
	if(fa==0 && ch>=2) cut[now]=1;
	if(!cut[now]) ans[now]=2*(n-1);
	else ans[now]+=(ll)(n-sum-1)*(sum+1)+(n-1); 
	return;
} 
int tong[N],sum[N];
signed main(){
	// step 1、读题、声明变量
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	// step 2、输入
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	// step 3、处理
	dfs(1,0);
	// step 4、输出
	/**
	for(int i=1;i<=n;i++){
		if(cut[i]){
			cout<<dfn[i]<<'\n';
			for(int j=1;j<=n;j++){
				if(j==i) continue;
				cout<<low[j]<<' ';
			}
			cout<<'\n';
		}
	}*/
	//for(int i=1;i<=n;i++) tong[low[i]]++;
	//for(int i=1;i<=n;i++) sum[i]=sum[i-1]+tong[i];
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<'\n';
		/**
		if(!cut[i]) cout<<2*(n-1)<<'\n';
		else{
			if(i==1){
				int rest=m-g[1].size();
				
			}
			//cout<<i<<'\n';
			int now_dfn=dfn[i],now_low=low[i];
			int less=sum[now_dfn-1];
			if(now_low<now_dfn) less--;
			int more=n-less-1;
			int ans=2*(less*more+n-1);
			//cout<<less<<' '<<more<<'\n';
			cout<<ans<<'\n';
		}*/
	}
	return 0;
}

*/ } return 0; }

2025/7/24 17:43
加载中...