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

using namespace std;

// process3 oraz query ze strony http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
int P[400100][20];

void process3(int N, int* T)
{
      int i, j;
   
  //we initialize every element in P with -1
      for (i = 1; i <= N; i++)
          for (j = 0; 1 << j < N; j++)
              P[i][j] = -1;
   
  //the first ancestor of every node i is T[i]
      for (i = 1; i <= N; i++)
          P[i][0] = T[i];
   
  //bottom up dynamic programing
      for (j = 1; 1 << j < N; j++)
         for (i = 1; i <= N; i++)
             if (P[i][j - 1] != -1)
                 P[i][j] = P[P[i][j - 1]][j - 1];
//for (int i=1;i<=N;i++) {for (int j=0;j<N;j++) printf("%d ", P[i][j]); printf("\n");}
}

int query(int N, int * T, int *L, int p, int q)
{
      int tmp, log, i;
   
  //if p is situated on a higher level than q then we swap them
      if (L[p] < L[q])
          tmp = p, p = q, q = tmp;
  
  //we compute the value of [log(L[p)]
      for (log = 1; 1 << log <= L[p]; log++);
      log--;
   
  //we find the ancestor of node p situated on the same level
  //with q using the values in P
      for (i = log; i >= 0; i--)
          if (L[p] - (1 << i) >= L[q])
              p = P[p][i];
   
      if (p == q)
          return p;
   
  //we compute LCA(p, q) using the values in P
      for (i = log; i >= 0; i--)
          if (P[p][i] != -1 && P[p][i] != P[q][i])
              p = P[p][i], q = P[q][i];
   
      return T[p];
}

int main() {
int n,m,k;
scanf("%d %d %d", &n, &m, &k);
long long g[n+5];
for (int i=1;i<=n;i++) scanf("%lld", g+i);
long long result = 0;
int* level = new int[n+m+5];
int* root =  new int[n+m+5];
int* parent =  new int[n+m+5];
int* mapa = new int[n+10];
int* dziecko_1 = new int[n+m+5];
int* dziecko_2 = new int[n+m+5];
for (int i=0;i<=n+m;i++) {level[i]=0; dziecko_1[i]=-1; dziecko_2[i] = -1; parent[i]=-1;}
for (int i=1;i<=n;i++) mapa[i] = i;
// budujemy drzewo
for (int i=1;i<=m;i++) {
int a, b;
scanf("%d %d", &a, &b);
parent[mapa[a]]=n+i;
parent[mapa[b]]=n+i;
dziecko_1[n+i] = mapa[a];
dziecko_2[n+i] = mapa[b];
mapa[b]=n+i;
}
//printf("Drzewo: "); for (int i=1;i<=n+m;i++) printf("%d ", parent[i]); printf("\n");
// przypisanie poziomu (BFS)
queue<int> q;
for (int i=1;i<=n+m;i++) if (parent[i]==-1) {q.push(i); level[i]=1;}
while (!q.empty()) {
int node = q.front();
q.pop();
if (level[node] == 0) level[node] = level[parent[node]] + 1;
if (dziecko_1[node] != -1) q.push(dziecko_1[node]); 
if (dziecko_2[node] != -1) q.push(dziecko_2[node]);
}
//printf("Poziomy: "); for (int i=1;i<=n+m;i++) printf("%d ", level[i]); printf("\n");
//szukamy LCA i liczymy wynik
process3(n+m, parent);
vector< pair<pair<int,int>, pair<int, int> > > reakcje;
for (int i=0;i<k;i++) {
int c, d;
scanf("%d %d", &c, &d);
int lca = query(n+m, parent, level, c, d);
//printf("LCA(%d, %d) = %d\n", c, d, lca);
reakcje.push_back(make_pair(make_pair(lca, i), make_pair(c, d)));
}
sort(reakcje.begin(), reakcje.end());
for (int i=0;i<k;i++) {
if (reakcje[i].first.first!=-1) {
long long osad = min(g[reakcje[i].second.first], g[reakcje[i].second.second]);
//printf("osad(%d, %d): %lld\n", reakcje[i].second.first, reakcje[i].second.second, osad);
result += 2*osad;
g[reakcje[i].second.first] -= osad;
g[reakcje[i].second.second] -= osad;
}
}

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