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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct L {
	int a, b, t, id;
};
int n, m, k, a, b, g [200002], akt [200002], cur, ojc [400004], p [400004] [20], gl [400004], lc, max_gl;
long long int ret;
vector <int> G [400004];
L l [500000];

void dfs (int aktn = 0, int ojcn = 0, int g = 0) {
	gl [aktn] = g;
	ojc [aktn] = ojcn;
	p [aktn] [0] = ojc [aktn];
	for (int i = 1; i < 20; i ++) p [aktn] [i] = p [p [aktn] [i-1]] [i-1];
	for (int i = 0; i < G[aktn].size (); i ++) dfs (G [aktn] [i], aktn, g + 1);
}
int lca (int a, int b) {
	if (gl [a] < gl [b]) swap (a, b);
	while (gl [a] != gl [b]) a = ojc [a];
	if (a == b) return a;
	
	int temp;
	while (ojc [a] != ojc [b]) {
		temp = 19;
		while (p [a] [temp] == p [b] [temp]) temp --;
		a = p [a] [temp];
		b = p [b] [temp];
	}
	return ojc [a];
}
bool cmp (L a, L b) {
	if (a.t < b.t) return true;
	if (a.t == b.t && a.id < b.id) return true;
	return false;
}

int main () {
	scanf ("%d %d %d", &n, &m, &k);
	cur = n;
	for (int i = 1; i <= n; i ++) {
		scanf ("%d", &g [i]);
		akt [i] = i;
	}
	for (int i = 1; i <= m; i ++) {
		scanf ("%d %d", &a, &b);
		
		cur ++;
		G [cur].push_back (akt [a]);
		G [cur].push_back (akt [b]);
		akt [b] = cur;
	}
	for (int i = 1; i <= cur; i ++) {
		if (ojc [i] == 0) G [0].push_back (i);
	}
	dfs ();
	for (int i = 0; i <= cur; i ++) max_gl = max(max_gl, gl [i]);
//IMPORTANT LCS MUUUSIC BYĆ INNY NIŻ 0 żeby liczył
	for (int i = 0; i < k; i ++) {
		scanf ("%d %d", &l [i].a, &l [i].b);
		lc = lca (l [i].a, l [i].b);
		if (lc == 0) {
			i --;
			k --;
		} else {
			l [i].t = max_gl - gl [lc];
			l [i].id = i;
		}
	}
	sort (l, l+k, cmp);
	for (int i = 0; i < k; i ++) {
		lc = min (g [l [i].a], g [l [i].b]);
		ret = ret + (long long int) (2*lc);
		g [l [i].a] -= lc;
		g [l [i].b] -= lc;
	}
	printf ("%lld\n", ret);
}