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

using namespace std;

vector<bool> colored;
vector<int> ancestor, c, d, g, parent, root, left_child, right_child;
vector<vector<pair<int, int> > > catalysts;
vector<vector<int> > reactions;

void MakeSet(const int u) {
  parent[u] = -1;
}

int Find(const int x) {
  if (parent[x] < 0) return x;
  parent[x] = Find(parent[x]);
  return parent[x];
}

void Union(const int x, const int y) {
  const int x_root = Find(x);
  const int y_root = Find(y);
  if (x_root == y_root) return;
  if (parent[x_root] < parent[y_root]) {
    parent[x_root] += parent[y_root];
    parent[y_root] = x_root;
  } else {
    parent[y_root] += parent[x_root];
    parent[x_root] = y_root;
  }
}

// http://pl.wikipedia.org/wiki/Algorytm_Tarjana
void TarjanOLCA(const int u) {
  MakeSet(u);
  ancestor[u] = u;
  if (left_child[u] != -1) {
    TarjanOLCA(left_child[u]);
    Union(u, left_child[u]);
    ancestor[Find(u)] = u;
  }
  if (right_child[u] != -1) {
    TarjanOLCA(right_child[u]);
    Union(u, right_child[u]);
    ancestor[Find(u)] = u;
  }
  colored[u] = true;
  for (int i = 0; i < catalysts[u].size(); ++i) {
    const int v = catalysts[u][i].second;
    if (colored[v]) reactions[ancestor[Find(v)]].push_back(catalysts[u][i].first);
  }
}

long long RunSimulation(const int u) {
  long long ret = 0;
  if (left_child[u] != -1) ret += RunSimulation(left_child[u]);
  if (right_child[u] != -1) ret += RunSimulation(right_child[u]);
  sort(reactions[u].begin(), reactions[u].end());
  for (int i = 0; i < reactions[u].size(); ++i) {
    const int substance_1 = c[reactions[u][i]];
    const int substance_2 = d[reactions[u][i]];
    const int amount = min(g[substance_1], g[substance_2]);
    ret += 2 * amount;
    g[substance_1] -= amount;
    g[substance_2] -= amount;
  }
  return ret;
}

void RecomputeRoot(const int a, const int b) {
  root[a] = b;
  if (left_child[a] != -1) RecomputeRoot(left_child[a], b);
  if (right_child[a] != -1) RecomputeRoot(right_child[a], b);
}

int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  g.resize(n);
  root.resize(n);
  left_child.resize(n);
  right_child.resize(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &g[i]);
    root[i] = i;
    left_child[i] = -1;
    right_child[i] = -1;
  }
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    // Add tree nodes.
    // cerr << a << '(' << root[a] << ")+" << b << '(' << root[b] << ")->" << root.size() << endl;
    assert(root[a] != root[b]);
    left_child.push_back(root[a]);
    right_child.push_back(root[b]);
    root[root[a]] = -1;
    root[root[b]] = -1;
    root[a] = root.size();
    root[b] = root.size();
    root.push_back(root.size());
  }

  for (int i = 0; i < root.size(); ++i) if (root[i] == i) RecomputeRoot(i, i);

  ancestor.resize(root.size());
  catalysts.resize(root.size());
  colored.resize(root.size());
  parent.resize(root.size());
  reactions.resize(root.size());

  c.resize(k);
  d.resize(k);
  for (int i = 0; i < k; ++i) {
    scanf("%d%d", &c[i], &d[i]);
    --c[i];
    --d[i];
    // Prepare LCA computation for c & d.
    if (root[c[i]] == root[d[i]]) {
      // cerr << "Reaction " << c << ' ' << d << endl;
      catalysts[c[i]].push_back(make_pair(i, d[i]));
      catalysts[d[i]].push_back(make_pair(i, c[i]));
    }
  }

  // Compute LCA and prepare reaction lists.
  for (int i = 0; i < root.size(); ++i) if (root[i] == i) TarjanOLCA(i);
  // Compute the answer.
  long long ret = 0;
  for (int i = 0; i < root.size(); ++i) if (root[i] == i) ret += RunSimulation(i);
  printf("%lld\n", ret);
  return 0;
}