类似一个貌似叫星球大战的题，拆边变成倒着加边方便计算，这里的 sz[] 数组的意义不是并查集有多少元素，而是并查集内有多少已经真正恢复的点。由于笔者不想写太多，就贴代码供参考。够精简的。

#include<bits/stdc++.h>
using namespace std;
int n,m,t[200005],f[200005],vis[200005],sz[200005];
long long ans[200005],sum;
string s;
vector<int>e[200005];
int fd(int x){
	return (f[x]==x?x:f[x]=fd(f[x]));
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)t[i]=s[i-1]-'0',f[i]=i;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v),e[v].push_back(u);
		if(t[u]&&t[v]){
			int fu=fd(u),fv=fd(v);
			if(fu==fv)continue;
			f[fu]=fv;
		}
	}
	for(int i=n;i>=1;i--){
		for(int v:e[i]){
			if(vis[v]==1||t[v]==1){
				int fi=fd(i),fv=fd(v);
				if(fv==fi)continue;
				f[fi]=fv,sum+=1ll*sz[fv]*sz[fi],sz[fv]+=sz[fi];
			}
		}
		vis[i]=1;
		int fi=fd(i);
		sum+=sz[fi],sz[fi]++;
		ans[i]=sum;
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
	return 0;
} 

https://blog.csdn.net/tenkuo/article/details/153462667