T0944 连通点对

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> fa, sz;
    long long pairs = 0;              // 连通的无序点对数
    explicit DSU(int n) : fa(n + 1), sz(n + 1, 1) {
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
    void merge(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        pairs += 1LL * sz[x] * sz[y];   // 合并后新增的连通点对
        fa[y] = x; sz[x] += sz[y];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    string c;
    cin >> c;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    DSU dsu(n);
    vector<long long> ans(n + 1, 0);

    // 倒着做：每次把点 i 放回图里
    for (int i = n; i >= 1; i--) {
        for (int v : adj[i]) {
            if (v > i) dsu.merge(i, v);          // 放回点 i 时补上它与更大编号邻居的边
        }
        // 关闭点 i-1 时（c[i-1]=='1'）要把 i-1 的邻居两两连边
        if (i >= 2 && c[i - 2] == '1') {
            vector<int> nb;
            for (int v : adj[i - 1]) if (v >= i) nb.push_back(v);
            for (size_t k = 1; k < nb.size(); k++) dsu.merge(nb[0], nb[k]);
        }
        ans[i] = dsu.pairs;
    }

    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
    return 0;
}