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<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<list>
#include<math.h>
#include<algorithm>
#include<string>
#include<set>
#include<queue>
#define limit 200015
#define inf 9223372036854775807ll
#define iinf 2147483647
#define mp make_pair
#define pb push_back
#define rep(i,k,n) for(int i=k;i<n;i++)
using namespace std;
int amount[limit],out[limit],num[limit];
long long res=0;
vector<vector<int> > chi(limit);
vector<vector<pair<int,int> > > ans(2000000);
vector<vector<set<pair<int,pair<int,int> > > > > reacts(limit);
vector<int> code;
vector<int> code1;
vector<vector<int> > apps(limit);
void dfs(int v,int lvl){
    ans[code.size()].pb(mp(lvl,v));
    code.pb(lvl);
    apps[v].pb(code1.size());
    code1.pb(v);
    rep(i,0,chi[v].size()){
        dfs(chi[v][i],lvl+1);
        ans[code.size()].pb(mp(lvl,v));
        code.pb(lvl);
        code1.pb(v);
    }
}
void dfs1(int v){
    rep(i,0,chi[v].size()){
        dfs1(chi[v][i]);
        if(v) for(set<pair<int,pair<int,int> > >::iterator it=reacts[v][i].begin();it!=reacts[v][i].end();it++){
            int react=min(amount[(*it).second.first],amount[(*it).second.second]);
            res+=2*react;
            amount[(*it).second.first]-=react;
            amount[(*it).second.second]-=react;
        }
    }
}
int main(){
    int n,m,k,temp1,temp2,temp3,temp4;
    scanf("%d%d%d",&n,&m,&k);
    rep(i,1,n+1) scanf("%d",&amount[i]);
    rep(i,0,m){
        scanf("%d%d",&temp1,&temp2);
        out[temp1]++;
        num[temp1]=chi[temp2].size();
        chi[temp2].pb(temp1);
    }
    rep(i,1,n+1) if(!out[i]) chi[0].pb(i);
    rep(i,0,n+1) reacts[i].resize(chi[i].size());
    dfs(0,0);
    for(int j=1;j<code.size();j*=2) for(int k=0;k+2*j-1<code.size();k++) ans[k].pb(min(ans[k].back(),ans[k+j].back()));
    rep(i,1,k+1){
        scanf("%d%d",&temp3,&temp4);
        temp1=apps[temp3].back();
        temp2=apps[temp4].back();
        if(temp1>temp2) swap(temp1,temp2);
        int d=int(log2(temp2-temp1)),lca;
        if(ans[temp1][d].first<ans[temp2-int(pow(2,d))][d].first) lca=ans[temp1][d].second;
        else lca=ans[temp2-int(pow(2,d))][d].second;
        vector<int>::iterator it=lower_bound(apps[lca].begin(),apps[lca].end(),temp2);
        --it;
        reacts[lca][num[code1[(*it)+1]]].insert(mp(i,mp(temp3,temp4)));
    }
    dfs1(0);
    printf("%lld",res);
    return 0;
}