2019牛客多校E.All men are brothers(そして調査集+配列組合せ)

連続エッジを並べて調べる過程を与え,連続エッジのたびに同じ集合内にない4つの選択法を選択する.
ごみ文科生はまた組み合わせられて授業を受けた.
まずこの問題は直接計算してもまったく計算できないので,1辺もないときの選び方がCn 4であることがわかりやすいので,毎回連辺の損失を計算することが考えられる.
では、連辺損失のたびに選ばれるのが、この2つのセット契約の時に人を選ぶ場合です.
どう計算しますか.まず、この2つの集合(k 1,k 2)を1人ずつ選択し、選択法は集合の大きさに乗算する.その後、残りの集合から2人を選択し、同一集合内から選択できないことを考慮しなければ、選択法はC(n-k 1-k 2)2であり、この組合せ数内のすべての同一集合内の選択法を減じる限り、残りの選択法である.この値は動的に維持でき,2つの集合を統合し,この2つの集合の共有を削減し,新しい集合の共有を加えるだけでよい.

#include 

using namespace std;
typedef unsigned long long ll;

const int maxn = 1e5 + 5;

int n, m;
int f[maxn];
ll sz[maxn];

ll ans, sum;

ll C2(ll x) {
    if (x <= 1) {
        return 0;
    }
    return x * (x - 1) / 2;
}

void init() {
    for (int i = 1; i <= n; ++i) {
        f[i] = i, sz[i] = 1;
    }
}

int find(int x) {
    if (x == f[x]) {
        return x;
    }
    return f[x] = find(f[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        int a = sz[x], b = sz[y];
        ans = ans - (sz[x] * sz[y]) * (C2(n - sz[x] - sz[y]) - sum + C2(sz[x]) + C2(sz[y]));
        sum = sum - C2(sz[x]) - C2(sz[y]);
        sum = sum + C2(sz[x] + sz[y]);
        f[y] = x;
        sz[x] += sz[y];
    }
}

int main() {
    scanf("%d%d", &n, &m);
    init();
    ans = 1ULL * n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4;
    printf("%llu
", ans);
    int a, b;
    while (m--) {
        scanf("%d%d", &a, &b);
        merge(a, b);
        printf("%llu
", ans);
    }
    return 0;
}