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
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int ileW, ileK, ileR, ilosc[200005], ob[200005], a, b, GL, gr[200005], rodzic[200005];
bool lisc[200005];
unsigned long long int suma;
vector<int> krawedzie[200005], reakcje[200005];
vector< pair<int,int> > rreakcje[200005];
set <int> s;


int lca(int u, int v){
	//printf("RODZIC[%d]=%d RODZIC[%d]=%d",a,rodzic[a],b,rodzic[b]);
	if(s.size()>0) 
		s.clear();
	if(u!=0) s.insert(u); if(v!=0) s.insert(v);
	while(u!=v){
		if(u!=0) { u=rodzic[u]; if(s.find(u)!=s.end()) return u; s.insert(u); }
		if(v!=0) { v=rodzic[v]; if(s.find(v)!=s.end()) return v; s.insert(v); }
	}
	return u;
}

void bfs(int x){
	ob[x]=ilosc[x];
	//printf("WCHODZE DO %d\n",x);
	gr[x]=GL;
	for(vector <int> :: iterator it=krawedzie[x].begin(); it!=krawedzie[x].end(); ++it)
	{
		bfs(*it);
	for(vector < pair<int,int> > :: iterator ik=rreakcje[x].begin(); ik!=rreakcje[x].end(); ++ik){
		if(ob[(*ik).first]>ob[(*ik).second]){
			//printf("REAKCJA %d --> %d, +%d\n",(*ik).first,(*ik).second,ob[(*ik).second]);
			ob[(*ik).first]-=ob[(*ik).second];
			suma+=ob[(*ik).second]; suma+=ob[(*ik).second];
			ob[(*ik).second]=0;
		}
		else{
		//	printf("REAKCJA %d --> %d, +%d\n",(*ik).second,(*ik).first,ob[(*ik).first]);
			ob[(*ik).second]-=ob[(*ik).first];
			suma+=ob[(*ik).first]; suma+=ob[(*ik).first];
			ob[(*ik).first]=0;
		}
	}		
	}

	//printf("WYCHODZE Z %d\n",x);
}

int main(){
	scanf("%d %d %d", &ileW, &ileK, &ileR);
	for(int i=1; i<=ileW; i++)
		scanf("%d", &ilosc[i]);
	for(int i=0; i<ileK; i++){
		scanf("%d %d", &a, &b);
		krawedzie[b].push_back(a);
		rodzic[a]=b;
		lisc[a]=true;
	}		
	for(int i=0; i<ileR; i++){
		scanf("%d %d", &a, &b);
		//printf("LCA(%d,%d)=%d\n",a,b,lca(a,b));
		rreakcje[lca(a,b)].push_back(make_pair(a,b));
		//reakcje[a].push_back(b);
		//reakcje[b].push_back(a);
	}
	for(int i=1; i<=ileW; i++)
		if(!lisc[i]){
			GL=i;	
			bfs(i);
		}
	printf("%llu",suma);
	return 0;
}