链接：https://ac.nowcoder.com/acm/contest/889/E?&headNav=acm&headNav=acm
来源：牛客网
 

题目描述

Amy asks Mr. B  problem E. Please help Mr. B to solve the following problem.

 

There are n people, who don't know each other at the beginning.

There are m turns. In each turn, 2 of them will make friends with each other.

The friend relation is mutual and transitive.

If A is a friend of B, then B is also a friend of A.

For example, if A is a friend of B, B is a friend of C, then A and C are friends.

At the beginning and after each turn, please calculate the number of ways to select four people from, such that any two of these four are not friends.

 

输入描述:

The first line contains two integers, n and m (n <= 100000, m <= 200000), which are the number of people, and the number of turns.

In the following m lines, the i-th line contains two integers x and y ( 1 <= x <= n, 1 <= y <= n, x ≠ y), which means the x-th person and the y-th person make friends in the i-th turn.

The x-th person and y-th person might make friends in several turns.

输出描述:

Output m+1 lines, each line contains an integer, which is the number of quadruples.

Output at the beginning and after each turn, so there are m+1 lines.

示例1

输入

6 6
1 2
3 4
4 5
3 5
3 6
2 4

输出

15
9
4
0
0
0
0

示例2

输入

100000 0

输出

4166416671249975000

说明

Don't use int.

题意：有n个人，最初互不认识。有q组交朋友，每组x，y，表示xy交朋友。每一次，输出从n个人中挑4个人，四个人互不认识有多少种可能。

思路：并查集维护朋友关系。假设上一次xy并不认识，而这一次xy认识了，那么答案肯定会减少。减少多少呢？减少的是从x所在集合取一个人，从y所在集合取一个人，再从剩下的集合任选两个集合从中挑两个人。怎么求呢？假设剩下集合大小为a，b，c...。那么从剩下的挑2个就有ab+ac+bc+...种可能，公式：ab+ac+bc+...=((a+b+c+.....)^2-(a*a+b*b+c*c+.....))/2;

假设sum1=a+b+c+....，sum2=a*a+b*b+c*c+.....。a,b合并后sum1不变，sum2=sum2-a*a-b*b+(a+b)^2=sum2+a*a*b；再维护一个sum2就行。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn=1e5+10;
int pre[maxn];
ll sum1,sum2,n,ans,num[maxn];
int find(int x)
{
	if(pre[x]!=x) pre[x]=find(pre[x]);
	return pre[x];
}
void merge(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx!=fy) pre[fx]=fy;
	if(fx==fy) return ;
	ans=ans-num[fx]*num[fy]*((sum1-num[fx]-num[fy])*(sum1-num[fx]-num[fy])-(sum2-num[fx]*num[fx]-num[fy]*num[fy]))/2;
	sum2+=2*num[fx]*num[fy];
	num[fy]+=num[fx];
	num[fx]=0;
}
int main()
{
	int m,x,y;
	scanf("%lld%d",&n,&m);
	sum1=sum2=n;
	for(int i=1;i<=n;i++) pre[i]=i,num[i]=1;
	ans=n*(n-1)/2*(n-2)/3*(n-3)/4;
	printf("%lld\n",n>=4?ans:0);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		merge(x,y);
		printf("%lld\n",ans);
	}
	return 0;
}