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
#include<stdio.h>
#include<vector>
#include<algorithm>
#define st first
#define nd second
using namespace std;
int z1[500000],z2[500000],lca[500000],pre[200000],pos[200000],t;
vector<int>q[200000],root;
bool wyl[200000];
vector<int>v[200000],koszt[500000];
void pre_pos(int x){
	pre[x]=t;
	t++;
	for(int i=0;i<v[x].size();i++)pre_pos(v[x][i]);
	pos[x]=t;
	t++;
}
bool ojc(int a,int b){
	return (pre[a]<=pre[b]&&pos[a]>=pos[b]);	
}
vector<int>kol;
int odpowiedz(int v){
	//cout<<"szukam lca "<<v<<" w ";
	//for(int i=0;i<kol.size();i++)cout<<kol[i]<<" ";
	//cout<<"\n";
	if(!ojc(kol[0],v))return -1;
	int p=0,k=kol.size()-1,s;
	while(p+1<k){
		s=(p+k)/2;
		if(ojc(kol[s],v))p=s;
		else k=s-1;
	}
	if(ojc(kol[k],v))return kol[k];
	else return kol[p];
}
int dfs_lca(int x){
	kol.push_back(x);	
	for(int i=0;i<q[x].size();i++){
		lca[q[x][i]]=odpowiedz(z2[q[x][i]]);	
	}
	for(int i=0;i<v[x].size();i++)dfs_lca(v[x][i]);
	kol.pop_back();
}
int waga[200000];
main(){
t=0;
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n;i++)scanf("%d",&waga[i]);
for(int i=0;i<m;i++){
	int a,b;
	scanf("%d%d",&a,&b);
	a--;b--;
	wyl[a]=1;
	v[b].push_back(a);
	koszt[b].push_back(i);
}
for(int i=0;i<k;i++){
	scanf("%d%d",&z1[i],&z2[i]);
	z1[i]--;z2[i]--;
	q[z1[i]].push_back(i);
}
for(int i=0;i<n;i++)if(!wyl[i])root.push_back(i);
for(int i=0;i<root.size();i++)pre_pos(root[i]);
for(int i=0;i<root.size();i++)dfs_lca(root[i]);
vector<pair<int,int> >zapyt;
//for(int i=0;i<k;i++)cout<<"lca "<<z1[i]<<" "<<z2[i]<<" to "<<lca[i]<<"\n";
for(int i=0;i<k;i++){
	if(lca[i]==-1)continue;
	int tura=0;
	for(int j=0;j<v[lca[i]].size();j++){
		if(ojc(v[lca[i]][j],z1[i]))tura=max(tura,koszt[lca[i]][j]);
		if(ojc(v[lca[i]][j],z2[i]))tura=max(tura,koszt[lca[i]][j]);
	}
	zapyt.push_back(make_pair(tura,i));
}
sort(zapyt.begin(),zapyt.end());
long long wynik=0;
for(int i=0;i<zapyt.size();i++){
	int tmp=min(waga[z1[zapyt[i].nd]],waga[z2[zapyt[i].nd]]);
	wynik+=tmp*2;
	waga[z1[zapyt[i].nd]]-=tmp;
	waga[z2[zapyt[i].nd]]-=tmp;
}
printf("%lld\n",wynik);
}