题面：
题解：一个非常显然的想法就是倒着一座桥一座桥地连，如果一座桥连通了原本不相连的两个块，毁灭数对的数量就要减去两个块中元素个数的数量之积。
#include <bits/stdc++.h> using namespace std; #define ll long long ll a[100005], b[100005], ans[100005], cnt[100005], fa[100005]; ll find(ll x) {return x == fa[x] ? x : fa[x] = find(fa[x]);} main() { ll n, m; scanf("%lld%lld", &n, &m); for (ll i = 1; i <= n; i++) cnt[i] = 1, fa[i] = i; for (ll i = m; i; i--) scanf("%lld%lld", &a[i], &b[i]); ll now = 1ll * (n - 1) * n / 2; for (ll i = 1; i <= m; i++) { ll fx = find(a[i]), fy = find(b[i]); if (fx == fy) ans[i] = now; else { ans[i] = now; now -= 1ll * cnt[fx] * cnt[fy]; fa[fx] = fy, cnt[fy] += cnt[fx]; } } for (ll i = m; i; i--) printf("%lld\n", ans[i]); }