题解 | 小红的图上加边

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;

struct UF {
    ll rank = 0;
    UF* root;
    ll w;
    ll n_max;
};

UF a[N];

UF* Root(UF* a) {
    if (a->root != a) {
        a->root = Root(a->root);
    }
    return a->root;
}

void merge(ll x, ll y) {
    UF* rx = Root(&a[x]);
    UF* ry = Root(&a[y]);
    if (rx == ry)return;
    if (rx->rank < ry->rank) {
        rx->root = ry;
        ry->n_max = max(ry->n_max, rx->n_max);
    } else {
        ry->root = rx;
        rx->n_max = max(ry->n_max, rx->n_max);
        if (rx->rank == ry->rank) {
            rx->rank++;
        }
    }
}



int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, m;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i].w;
        a[i].n_max = a[i].w;
        a[i].root = &a[i];
    }
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        merge(u, v);
    }

    unordered_set<UF*>s;
    multiset<ll>ans;
    for (ll i = 1; i <= n; i++) {
        UF* t = Root(&a[i]);
        if (s.find(t) == s.end()) {
            ans.insert(t->n_max);
            s.insert(t);
        }
    }
    bool f = 0;
    ll p = 0;
    for (auto t : ans) {
        if (f == 0) {
            f = 1;
            continue;
        }
        p += t;
    }
    cout << p;

    return 0;
}