AT4319
hxhhxh
·
·
题解
大意
$$ \sum_{i=1}^n \sum_{j=i+1}^n con(i,j) $$
## 思路
反向操作，问题转化为每一次连一条边，求答案
用带权并查集，每一次连接会减少 $ size(a) \times size(b) $ 对联通点。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[100005],siz[100005],n,m,ea[100005],eb[100005],ans[100005];
int dfs(int x){
if(f[x]==x) return x;
return f[x]=dfs(f[x]);
}
signed main(){
cin>>n>>m;
int an=0;
for(int i=1;i<=n;i++) f[i]=i,siz[i]=1;
for(int i=1;i<=m;i++) scanf("%lld %lld",&ea[i],&eb[i]);
for(int i=m;i>=1;i--){
ans[i]=an;
if(dfs(ea[i])!=dfs(eb[i])){
int sa=siz[dfs(ea[i])],sb=siz[dfs(eb[i])];
an+=sa*sb;
siz[dfs(eb[i])]+=sa;
f[dfs(ea[i])]=dfs(eb[i]);
}
}
for(int i=1;i<=m;i++) printf("%lld\n",n*(n-1)/2-ans[i]);
return 0;
}
```