Decayed Bridges [AtCoder Beginner Contest 120 D]

https://atcoder.jp/contests/abc120/tasks/abc120_d

前提知識

• UnionFind

解説

https://atcoder.jp/contests/abc120/submissions/4460557

「連結を分離させていく操作は、時間を逆に見て連結させていく操作で考える」というテクを使う。
連結成分を分けることは難しいので、時間を逆に見ていくことにする。
つまり、分離によって不便さがどれだけ増えるかを考えるのではなく、連結によって不便さがどれだけ減るかを考える。
ある2つの連結成分があり、サイズがaとbだったら、その2つの連結成分が連結することで不便さはabだけ減る。
一番最初の不便さはN*(N-1)/2なので、ここから連結によって不便さを減らしていけば、その局面毎に不便さを計算可能。
あとは、連結しながら連結成分のサイズを保持する方法だが、これはUnionFindしながら情報を持つテクを使えばいい。

int N, M, A[101010], B[101010];
UnionFind uf(101010);
int cnt[101010];
ll ans[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }
    rep(i, 0, N) cnt[i] = 1;
 
    ans[M-1] = 1LL * N * (N - 1) / 2;
    rrep(i, M - 1, 1) {
        int a = A[i], b = B[i];
 
        if (uf[a] == uf[b]) ans[i - 1] = ans[i];
        else {
            ans[i - 1] = ans[i] - 1LL * cnt[uf[a]] * cnt[uf[b]];
            int sm = cnt[uf[a]] + cnt[uf[b]];
            uf(a, b);
            cnt[uf[a]] = sm;
        }
    }
 
    rep(i, 0, M) printf("%lld\n", ans[i]);
 
}