题目链接:https://ac.nowcoder.com/acm/contest/889/E
题意:给出m对朋友关系,朋友关系可以传递,每次给出一对朋友关系后,输出选择四个人两两都不是朋友的不同方案的数目
思路:考虑每次新添入一对朋友对答案得影响,利用组合数学可以得出当前答案,一直更新即可
代码:
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll Fa[100100];
ll sz[100100];
void init(int n)
{
for(int i=1;i<=n;i++){
Fa[i]=i;
sz[i]=1;
}
}
int fid(int x)
{
if(x==Fa[x]) return x;
return Fa[x]=fid(Fa[x]);
}
int main()
{
ll n,m;
scanf("%lld %lld",&n,&m);
init(n);
ll ans=n*(n-1)/2*(n-2)/3*(n-3)/4,s=0;
printf("%llu\n",ans);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d %d",&a,&b);
int fa=fid(a),fb=fid(b);
if(fa!=fb&&ans!=0){
s=s-(sz[fa]*(sz[fa]-1)/2+sz[fb]*(sz[fb]-1)/2);
ll k=n-sz[fa]-sz[fb];
ans=ans-(k*(k-1))/2*sz[fa]*sz[fb]+sz[fa]*sz[fb]*s;
s=s+(sz[fa]+sz[fb])*(sz[fa]+sz[fb]-1)/2;
Fa[fa]=fb;
sz[fb]+=sz[fa];
printf("%llu\n",ans);
}
else {
printf("%llu\n",ans);
}
}
}