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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// Parts of code adopted from http://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <deque>

#define REP(i, n) for (int i = 0; i < (n); ++i) 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i) 

using namespace std;

const int MAX_N = 200100;
const int MAX_K = 500100;
const char BLACK = 0;
const char WHITE = 1;

int n, m, k, z;
long long val[MAX_N];
vector<pair<int, int> > queries[MAX_N*2];

int renames[MAX_N*2];
int parent[MAX_N*2];

vector<int> G[MAX_N*2];
int ancestor[MAX_N*2];
int my_rank[MAX_N*2];
char color[MAX_N*2];

struct mix {
    int a, b, lca;
    mix() {}
    mix(int a_, int b_, int lca_) : a(a_), b(b_), lca(lca_) {}
};
vector<int> order[MAX_N*2];
mix qs[MAX_K];

void MakeSet(int x) {
    parent[x] = x;
    my_rank[x] = x;
}

int Find(int x) {
    if (parent[x] == x) {
        return x;
    }
    parent[x] = Find(parent[x]);  // FIXME: recursion
    return parent[x];
}

void Union(int x, int y) {
    int xRoot = Find(x);
    int yRoot = Find(y);
    if (my_rank[xRoot] > my_rank[yRoot]) {
        parent[yRoot] = xRoot;
    } else if (my_rank[xRoot] < my_rank[yRoot]) {
        parent[xRoot] = yRoot;
    } else if (xRoot != yRoot) {
        parent[yRoot] = xRoot;
        my_rank[xRoot] += 1;
    }
}

void tarjan(int u) {
    MakeSet(u);
    ancestor[u] = u;
    REP(i, G[u].size()) {
        int v = G[u][i];
        tarjan(v);  // FIXME: recursion
        Union(u, v);
        ancestor[Find(u)] = u;
    }
    color[u] = BLACK;
    REP(i, queries[u].size()) {
        int v = queries[u][i].first;
        int index = queries[u][i].second;

        if (color[v] == BLACK) {
            int lca = ancestor[Find(v)];
            qs[index] = mix(u, v, lca);
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &k);
    REP(i, n) scanf("%lld", &val[i]);
    REP(i, n+m+10) renames[i] = i;
    REP(i, n+m+10) parent[i] = i;

    // Read tree
    REP(i, m) {
        int x, y;
        scanf("%d %d", &x, &y);
        int rx = renames[x-1];
        int ry = renames[y-1];

        G[n+i].push_back(rx);
        G[n+i].push_back(ry);
        parent[rx] = n+i;
        parent[ry] = n+i;

        renames[y-1] = n+i;
    }

    // Top node, in case it's a forest.
    z = n + m + 1;
    REP(i, n+m) {
        if (parent[i] == i) {
            parent[i] = z-1;
            G[z-1].push_back(i);
        }
    }

    REP(i, z) color[i] = WHITE;

    REP(i, k) {
        int x, y;
        scanf("%d %d", &x, &y);
        x -= 1;
        y -= 1;
        queries[x].push_back(make_pair(y, i));
        queries[y].push_back(make_pair(x, i));
    }

    tarjan(z-1);

    REP(i, k) order[qs[i].lca].push_back(i);

    long long total = 0;
    REP(i, z-1) {
        REP(j, order[i].size()) {
            int a = qs[order[i][j]].a;
            int b = qs[order[i][j]].b;

            long long x = min(val[a], val[b]);
            val[a] -= x;
            val[b] -= x;
            total += 2*x;
        }
    }

    printf("%lld\n", total);
    return 0;
}