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
#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#define f first
#define s second
using namespace std;

const long long INF = 1000000000000000005ll;
const int size = 200005;

int n, m, k;
int W[size], P[size];
pair<int, int> K[500003];
vector<int> G[size], use[size];
vector<pair<int, int> > prepare[size];
int D[2000005], wys[size];
int M[size], H[2*size+4];;

int p = 1, tout = 0;
long long result = 0;

void count(int x) {
	for(int i = 0; i<prepare[x].size(); i++) {
		int where = prepare[x][i].f, nr = prepare[x][i].s;
		use[where].push_back(nr);
	}
	for(int i = 0; i<G[x].size(); i++) {
		count(G[x][i]);
		sort(use[x].begin(), use[x].end());
		for(int j = 0; j<use[x].size(); j++) {
			int a = K[use[x][j]].f, b = K[use[x][j]].s;
			int x = min(W[a],W[b]);
			result += (long long) 2*x;
			W[a] -= x; W[b] -= x;
		}
		vector<int>().swap(use[x]);
	}
}

int counter = 0;
int prepareLCA(int x, int h) {
	H[counter++] = x;
	M[x] = counter-1;
	wys[x] = h;
	for(int i = 0; i<G[x].size(); i++) {
		prepareLCA(G[x][i], h+1);
		H[counter++] = x;
	}
}

int getMin(int a, int b) {
	a += p-1;
	b += p-1;
	if(a > b) swap(a, b);
	if(a == b) return D[a];
	int result = (wys[D[a]] < wys[D[b]]) ? (D[a]) : (D[b]);
	//printf("result: %d\n", result);
	while((a-1)/2 != (b-1)/2) {
		if(a%2) result = (wys[D[a+1]] < wys[result]) ? (D[a+1]) : (result);
		if(b%2 == 0) result = (wys[D[b-1]] < wys[result]) ? (D[b-1]) : (result);
		a = (a-1)/2;
		b = (b-1)/2;
	}
	return result;
}

int LCA(int x, int y) {
	int s = getMin(M[x], M[y]);
	return s;
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 1; i<=n; i++) {
		scanf("%d", &W[i]);
	}
	for(int i = 0; i<=n; i++) {
		P[i] = 0;
		M[i] = -1;
	}
	for(int i = 0; i<m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		P[a] = b;
		G[b].push_back(a);
	}
	for(int i = 1; i<=n; i++) if(P[i] == 0) G[0].push_back(i);
	for(int i = 0; i<k; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		K[i] = make_pair(a, b);
	}
	prepareLCA(0, 0);
	p = 1;
	while(p<=counter) p *= 2;
	for(int i = 0; i<counter; i++) D[p-1+i] = H[i];
	for(int i = p-2; i>=0; i--) D[i] = (wys[D[2*i+1]] < wys[D[2*i+2]]) ? (D[2*i+1]) : (D[2*i+2]);
	for(int i = 0; i<k; i++) {
		int a = K[i].f, b = K[i].s;
		if(M[a] > M[b]) swap(a, b);
		int x = LCA(a, b);
		if(x == 0) continue;
		prepare[b].push_back(make_pair(x, i));
	}
	count(0);
	printf("%lld\n", result);
	return 0;
}