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