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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cstring>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define VI vector<int>
#define PII pair<int,int>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lint long long int
#define max_n 500005

using namespace std;

int n,m,k;
vector<PII> kolejnosc;
VI masa;
vector<PII> q[max_n];
int gdziejest[max_n];
VI graf[max_n];
int odp[max_n];
vector<PII> pytania;
VI reakcje[max_n];

//LCA UJTEAM

int p[max_n], anc[max_n],size[max_n];
bool col[max_n];

int set_find(int a) { return p[a]==a?a:p[a]=set_find(p[a]); }

int set_union(int a,int b){
	int x = set_find(a);
	int y = set_find(b);
	if(size[x]>size[y]){ p[y] = x; return x;}
	else if(size[y]>size[x]) { p[x]=y; return y;}
	else{
		p[y] = x;
		size[x]++;
	}
	return x;
}

void dfs(int u, int f) {
    FOREACH(v, graf[u]) if (*v!=f) {
        dfs(*v, u);
	int h = set_union(set_find(u),set_find(*v));
        anc[h] = u;
    }
    col[u] = true;
    FOREACH(i,q[u]) 
        if (col[i->first]) odp[(i->second)] = anc[set_find(i->first)];
}

void lca(int root) {
    FOR(i,0,n+m+1) { p[i]=anc[i]=i; col[i]=0; size[i] = 0; }
    dfs(root, -1);
}


int main(){
	scanf("%d%d%d",&n,&m,&k);
	FOR(i,0,n){
		int a; scanf("%d",&a); masa.pb(a);
	}
	FOR(i,0,m){
		int a,b; scanf("%d%d",&a,&b);
		kolejnosc.pb(mp(a-1,b-1));
	}
	FOR(i,0,k){
		int a,b; scanf("%d%d",&a,&b);
		q[a-1].pb(mp(b-1,i));
		q[b-1].pb(mp(a-1,i));
		pytania.pb(mp(a-1,b-1));
	}
	//BUDUJ DRZEWO 
	FOR(i,0,n) gdziejest[i] = i;
	FOR(i,n,n+m){
		int a = kolejnosc[i-n].st, b = kolejnosc[i-n].nd;
		int va = gdziejest[a], vb = gdziejest[b];
		graf[i].pb(va); graf[i].pb(vb);
		graf[va].pb(i); graf[vb].pb(i);
		gdziejest[a] = -1; gdziejest[b] = i;
	}
	FOR(i,0,n){
		if(gdziejest[i]!=-1){
			graf[gdziejest[i]].pb(n+m);
			graf[n+m].pb(gdziejest[i]);
		}
	}
	/*
	FOR(i,0,n+m+1){
		cout<<"GRAF sasiedzi "<<i<<endl;
		FOR(u,0,graf[i].size()) 
			cout<<graf[i][u]<<" ";
		cout<<endl;
	}*/
	//LCA
	lca(n+m);
	FOR(i,0,k) reakcje[odp[i]].pb(i);
	//KONCZ
	/*FOR(i,0,n+m+1){
		cout<<"REAKCJE W wierzcholku "<<i<<endl;;
		FOR(j,0,reakcje[i].size())
		}
	}*/
	lint res = 0;
	FOR(i,n,n+m){
		FOR(j,0,reakcje[i].size()){
			int a = pytania[reakcje[i][j]].st, b = pytania[reakcje[i][j]].nd;
			int c = min(masa[a],masa[b]);
			res+=2LL*c;
			masa[a]-=c; masa[b]-=c;
		}
	}
	printf("%lld\n",res);

}