1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
set < pair <int,int> > fiolki[ 200005 ];
vector < pair <int,int> > reakcje[ 200005 ];
vector < pair < int, pair <int,int> > > r;
vector < pair <int,int> > kol;
int n,m,k;
int parent[ 200005 ];
int find( int a ){
    if (parent[a] == a){
        return a;
    }
    else {
        parent[a] = find( parent[a] );
        return parent[a];
    }
}
void _union(int a, int b){
    a = find(a);
    b = find(b);
    parent[a] = b;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    long long sum = 0, sum2 = 0;
    for (int i = 1; i <= n; i++){
        parent[i] = i;
        int d;
        scanf("%d",&d);
        sum += d;
        fiolki[ i ].insert( make_pair( i, d ));
    }
    for (int i = 0; i < m; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        kol.push_back( make_pair(a,b) );
    }
    for (int i = 1; i <= k; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        reakcje[ a ].push_back( make_pair( b, i) );
        reakcje[ b ].push_back( make_pair( a, i) );
    }
    for (int i = 0; i < m; i++){
        int a = kol[i].first, b = kol[i].second;
        a = find(a);
        b = find(b);
        if (fiolki[a].size() < fiolki[b].size()){
            int t = a;
            a = b;
            b = t;
        }
        for (set < pair<int,int> >::iterator it = fiolki[ b ].begin(); it != fiolki[ b ].end(); it++){
            for (int j = 0; j < reakcje[ (*it).first ].size(); j++){
                set < pair <int,int> >::iterator it2 = fiolki[ a ].upper_bound( make_pair( reakcje[ (*it).first ][ j ].first, -1 ));
                if ((it2 != fiolki[ a ].end()) && ((*it2).first == reakcje[ (*it).first ][ j ].first)){
                    r.push_back( make_pair( reakcje[ (*it).first ][ j ].second, make_pair( (*it2).first , (*it).first )));
                }
            }
        }
        sort (r.begin(), r.end());
        for (int j = 0; j < r.size(); j++){
            set < pair <int,int> >::iterator it2 = fiolki[ a ].upper_bound( make_pair( r[ j ].second.first, -1 ) ), it = fiolki[ b ].upper_bound( make_pair( r[ j ].second.second, -1 ) );
            if ((it2 != fiolki[ a ].end()) && (it != fiolki[ b ].end()) && ((*it2).first == r[ j ].second.first) && ((*it).first == r[ j ].second.second)){
                if ((*it2).second > (*it).second){
                    pair <int,int> p1 = *it2, p2 = *it;
                    fiolki[b].erase( p2 );
                    fiolki[a].erase( p1 );
                    p1.second -= p2.second;
                    fiolki[a].insert( p1 );
                }
                else {
                    pair <int,int> p1 = *it2, p2 = *it;
                    fiolki[b].erase( p2 );
                    fiolki[a].erase( p1 );
                    p2.second -= p1.second;
                    fiolki[b].insert( p2 );
                }
            }
        }
        for (set < pair<int,int> >::iterator it = fiolki[b].begin(); it != fiolki[b].end(); it++){
            fiolki[a].insert( *it );
        }
        fiolki[b].clear();
        _union(b,a);
    }
    for (int i = 1; i <= n; i++){
        for (set < pair <int,int> >::iterator it = fiolki[ i ].begin(); it != fiolki[ i ].end(); it++){
            sum2 += (*it).second;
        }
    }
    printf("%lld\n", sum-sum2);
}