1795G - Removal Sequences - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define ff first 
#define ss second
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(v) ((int)v.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef unsigned long long ull;

void solve(){
    int n,m;
    cin >> n >> m;
    vi a(n+1);
    rep(i,1,n+1){
        cin >> a[i];
    }
    vector<vi> g(n+1,vi());
    rep(i,0,m){
        int a,b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    queue<int> q;
    vector<pii> ed;
    rep(i,1,n+1){
        a[i] = sz(g[i]) - a[i];
        if(a[i]==0)q.push(i),a[i]=-1;
    }
    while(!q.empty()){
        int v = q.front();
        q.pop();
        a[v]=-1;
        for(auto to : g[v])if(a[to]!=-1){
            ed.pb({v,to});
            a[to]--;
            if(a[to]==0)q.push(to);
        }
    }
    ll res = n*(ll)(n-1)/2 + n;
    vector<ull> mask(n+1);
    for(int l=1;l<=n;l+=64){
        int r = min(n,l+63);
        for(int i=l;i<=r;i++)mask[i] = 1LL<<(i-l);
        for(auto &e : ed){
            mask[e.ss]|=mask[e.ff];
        }
        for(int i=1;i<=n;i++){
            res -= __builtin_popcountll(mask[i]);
            mask[i]=0;
        }
    }
    cout << res << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}