#1196188 (C++23) No.3781 Erase One, Gain from the Other

• 問題: No.3781 Erase One, Gain from the Other
• ユーザー: yaaya
• 提出日時: 2026-10-31 00:24:27
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 291 ms / 2,000 ms
• コード長: 3,227 bytes
• コンパイル時間: 3,638 ms
• コンパイル使用メモリ: 366,912 KB
• 実行使用メモリ: 38,052 KB
• 最終ジャッジ日時: 2026-10-31 00:24:40
• 合計ジャッジ時間: 12,899 ms
• ジャッジサーバーID （参考情報）: judge7_0 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 34

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a-1;i>=b;i--)
#define ll long long
#define ull unsigned ll
#define ld long double
#define bl __int128_t
#define fi first
#define se second
#define vel vector<ll>
#define vvel vector<vel>
#define pll pair<ll,ll>
#define vepll vector<pll>
#define vvepll vector<vepll>
#define ves vector<string>
#define vem vector<mint>
#define vvem vector<vem>
#define pmm pair<mint,mint>
#define cleout(i) cout<<fixed<<setprecision(i)
template<class T>using PQ=priority_queue<T,vector<T>,greater<T>>;
//               上  右 下 左
vector<int> di={-1, 0, 1, 0};
vector<int> dj={ 0, 1, 0,-1};

vector<int> dx={ 0, 1, 0,-1};
vector<int> dy={ 1, 0,-1, 0};


vector<int> ddx={ 1, 1, 1, 0, -1, -1, -1, 0 };
vector<int> ddy={ 1, 0, -1, -1, -1, 0, 1, 1 };

ll inf=1000000000000000000;//1e18
// LLONG_MAX

mt19937_64 rng((ull)chrono::steady_clock::now().time_since_epoch().count());

struct Merge{//a->b
    inline void operator()(vepll &a,vepll &b){
        if(a.size()>b.size()){
            for(pll x:b)a.push_back(x);
            swap(a,b);
        }else{
            for(pll x:a)b.push_back(x);
        }
        return ;
    }
};

template<typename T,typename Merge>
struct UF{
    vel par;
    vvel siz;
    vector<T> val;
    int grp_size;
    Merge merge;
    UF(int N,T id){
        par.assign(N,0);
        siz.assign(N,{});
        val.assign(N,id);
        grp_size=N;
        rep(i,0,N){
            siz[i].push_back(i);
            par[i]=i;
        }
    }
    int root(int x){
        if(par[x]==x)return x;
        par[x]=root(par[x]);
        return par[x];
    }
    void unite(int y,int x){
        int rx=root(x);
        int ry=root(y);
        if(rx==ry) return ;
        grp_size--;
        if(siz[rx].size()>siz[ry].size()){
            for(auto v:siz[ry]){
                siz[rx].push_back(v);
            }
        }else{
            for(auto v:siz[rx]){
                siz[ry].push_back(v);
            }
            swap(siz[rx],siz[ry]);
        }
        siz[ry].clear();
        par[ry]=par[rx];
        merge(val[ry],val[rx]);
    }
    void add(int i,T x){
        merge(x,val[root(i)]);
    }
    T get(ll x){
        return val[root(x)];
    }
    int size(int x){
        return siz[root(x)].size();
    }
    const vel& grp(int x){
        return siz[root(x)];
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
};

void _solve(){
    ll N,M;
    cin>>N>>M;
    vel a(N);
    rep(i,0,N)cin>>a[i];
    priority_queue<pair<ll,pll>> pq;
    UF<vepll,Merge> tree(N+1,{});
    rep(i,0,M){
        ll u,v;
        cin>>u>>v;
        u--;
        v--;
        pq.push({a[u]+a[v],{u,v}});
    }
    rep(i,0,N)pq.push({a[i],{i,N}});
    ll ans=0;
    while(pq.size()){
        pll now=pq.top().se;
        ll c=pq.top().fi;
        pq.pop();
        if(tree.same(now.fi,now.se))continue;
        tree.unite(now.fi,now.se);
        ans+=c;
    }
    for(ll x:a)ans-=x;
    cout<<ans<<"\n";
}


int main(){
    cin.tie(nullptr);
 	ios_base::sync_with_stdio(false);
    
    ll _;
    bool multitest=1;
    if(multitest)cin>>_;
    else _=1;
    rep(__,0,_){
        _solve();
    }
}