一.题目链接：

All men are brothers

二.题目大意：

n 个人，m 次操作.

每次操作让两个人交朋友，朋友关系互逆且可传递.

每次操作后，输出四人组的种数，使得这四个人中每每两个人均不为朋友.

三.分析：

并查集很容易想到，这题其实可以用组合数学来解的，可惜我太菜，不会。。。

这里用线段树写一下.

tree[i][j] 代表第 i 个节点所包含的区间内，从中选出 j 个人且两两不为朋友的方案数.

详见代码.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;

const int M = (int)1e5;
const int mod = 99991;
const int inf = 0x3f3f3f3f;

ll tree[M * 4 + 5][5];
int fa[M + 5], sz[M + 5];

int tofind(int x)
{
    if(x != fa[x])
        fa[x] = tofind(fa[fa[x]]);
    return fa[x];
}

void push_up(int k)
{
    tree[k][1] = tree[lc][1] + tree[rc][1];
    tree[k][2] = tree[lc][1] * tree[rc][1] + tree[lc][2] + tree[rc][2];
    tree[k][3] = tree[lc][1] * tree[rc][2] + tree[lc][2] * tree[rc][1]
    + tree[lc][3] + tree[rc][3];
    tree[k][4] = tree[lc][1] * tree[rc][3] + tree[lc][3] * tree[rc][1] 
    + tree[lc][2] * tree[rc][2] + tree[lc][4] + tree[rc][4];
}

void build(int k, int l, int r)
{
    if(l == r)
    {
        tree[k][1] = 1;
        tree[k][2] = tree[k][3] = tree[k][4] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    push_up(k);
}

void update(int k, int l, int r, int pos, int v)
{
    if(l == r)
    {
        tree[k][1] = v;
        tree[k][2] = tree[k][3] = tree[k][4] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid)
        update(lc, l, mid, pos, v);
    else
        update(rc, mid + 1, r, pos, v);
    push_up(k);
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i)
        fa[i] = i, sz[i] = 1;
    int u, v;
    build(1, 1, n);
    printf("%lld\n", tree[1][4]);
    while((m--) > 0)
    {
        scanf("%d %d", &u, &v);
        u = tofind(u);
        v = tofind(v);
        if(u != v)
        {
            fa[v] = u;
            sz[u] += sz[v];
            update(1, 1, n, v, 0);
            update(1, 1, n, u, sz[u]);
        }
        printf("%lld\n", tree[1][4]);
    }
    return 0;
}