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
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int pojemnosci[200001];
int gdzie[200001];
int spojne[400001];
int ojciec[400001][21];
pair<int, int> kraw[400001];
vector<int> reakcje[400001];
int glebokosc[400001];
int tab[500001][2];
int main(){
	int n,m,k;
	scanf("%d%d%d", &n, &m, &k);
	for(int i=1; i<=n; i++){
		scanf("%d", &pojemnosci[i]);
		gdzie[i]=i;
		}
	int ile=n;
	for(int i=1; i<=m; i++){
		int a,b;
		scanf("%d%d", &a, &b);
		ile++;
		ojciec[gdzie[a]][0]=ile;
		ojciec[gdzie[b]][0]=ile;
		kraw[ile]=make_pair(gdzie[a], gdzie[b]);
		gdzie[a]=ile;
		gdzie[b]=ile;
		}
		int is=0;
		for(int i=ile; i>=1; i--){
			if(spojne[i]==0){
				is++;
				spojne[i]=is;
				glebokosc[i]=1;
				queue<int> kolejka;
				kolejka.push(i);
				while(!kolejka.empty()){
				int w=kolejka.front();
				kolejka.pop();	
				if(w>n){
					int x=kraw[w].first;
					spojne[x]=is;
					kolejka.push(x);
					glebokosc[x]=glebokosc[w]+1;
					x=kraw[w].second;
					glebokosc[x]=glebokosc[w]+1;
					spojne[x]=is;
					kolejka.push(x);
					}
				}	
			}
		}
	for(int i=1; i<=20; i++){
		for(int j=1; j<=ile; j++){
			ojciec[j][i]=ojciec[ojciec[j][i-1]][i-1];
			}
		}
		for(int i=1; i<=k; i++){
			int a,b;
			scanf("%d%d", &a, &b);
			if(spojne[a]==spojne[b]){
			int x=a, y=b;
			if(glebokosc[y]>glebokosc[x])
			swap(x,y);
			for(int j=20; j>=0; j--){
				if(glebokosc[ojciec[x][j]]>=glebokosc[y])
					x=ojciec[x][j];
				}
			for(int j=20; j>=0; j--){
				if(ojciec[x][j]!=ojciec[y][j]){
					x=ojciec[x][j];
					y=ojciec[y][j];
					}
				}
				while(x!=y){
					x=ojciec[x][0];
					y=ojciec[y][0];
					}
				reakcje[x].push_back(i);
				}
				tab[i][0]=a;
				tab[i][1]=b;
			}
			long long wyn=0;
	for(int i=1; i<=ile; i++){
		for(vector<int> :: iterator it=reakcje[i].begin(); it!=reakcje[i].end(); it++){
			int a=tab[*it][0];
			int b=tab[*it][1];
			long long x=min(pojemnosci[a], pojemnosci[b]);
			pojemnosci[a]-=x;
			pojemnosci[b]-=x;
			wyn+=2*x;
			}
		
		}
		printf("%lld", wyn);
	}