2019牛客暑期多校训练营（第九场）E：All men are brothers

题目链接：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);
       }
    }
}