树上差分求调

#include <bits/stdc++.h>
#define int long long
#define up(i, x, y) for(int i = x; i <= y; i ++ )
#define dn(i, x, y) for(int i = x; i >= y; i -- )
#define mst(a, b) memset(a, b, sizeof a)
using namespace std;
int read() {
  int ret = 0, sgn = 0, ch = getchar();
  while (!isdigit(ch)) sgn |= ch == '-', ch = getchar();
  while (isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
  return sgn ? -ret : ret;
}
void read1(int&a) { a = read(); }
void read2(int&a, int&b) { a = read(), b = read(); }
void read3(int&a, int&b, int&c) { a = read(), b = read(), c = read(); }
void read4(int&a, int&b, int&c, int&d) { a = read(), b = read(), c = read(), d = read(); }
const int N = 5e5 + 10, M = 2e6 + 10;
int n, m, a[N];
vector<int> e[N];
int bcc_cnt;
int dfn[N], low[N];
bool vis[N];
int col[N];
int scc; // scc ' s number
int sc[N]; // all val
int st[N], t;
void tarjan(int u, int fa) {
  low[u] = dfn[u] = ++bcc_cnt;
  st[ ++ t] = u, vis[u] = 1;
  for (auto v : e[u]) {
    if (v == fa) continue;
    if (!dfn[v])
      tarjan(v, u), low[u] = min(low[u], low[v]);
    else if (vis[v])
      low[u] = min(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    scc ++ ;
    while (st[t + 1] != u) {
      int x = st[t];
      col[x] = scc, sc[scc] += a[x];
      vis[x] = 0, t -- ;
    }
  }
}
int son[N], siz[N], dep[N], fa[N], cnt, top[N];
void dfs1(int o) {
  son[o] = -1, siz[o] = 1;
  for (auto i : e[o]) if (!dep[i]) {
    dep[i] = dep[o] + 1, fa[i] = o, dfs1(i), siz[o] += siz[i];
    if (son[o] == -1 || siz[i] > siz[son[o]]) son[o] = i;
  }
}
void dfs2(int o, int t) {
  top[o] = t;
  if (son[o] == -1) return;
  dfs2(son[o], t);
  for (auto i : e[o]) if (i != son[o] && i != fa[o]) dfs2(i, i);
}
int lca(int u, int v) {
  while (top[u] != top[v])
    if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
    else v = fa[top[v]];
  return dep[u] > dep[v] ? v : u;
}
int c[N];
int res;
void down(int x, int fa) {
  for (auto i : e[x]) if (fa - i) down(i, x), c[x] += c[i];
  if (c[x]) res += sc[x];
}
int u[N], v[N];
signed main() {
  read2(n, m);
  up(i, 1, n) read1(a[i]);
  up(i, 1, m) {
    read2(u[i], v[i]);
    e[u[i]].emplace_back(v[i]);
    e[v[i]].emplace_back(u[i]);
  }
  up(i, 1, n) {
    if (!dfn[i]) tarjan(i, -1);
    e[i].clear();
  }
  up(i, 1, m) if (col[u[i]] - col[v[i]]) {
    e[col[v[i]]].emplace_back(col[u[i]]);
    e[col[u[i]]].emplace_back(col[v[i]]);
  }
  dep[1] = 1;
  dfs1(1);
  dfs2(1, 1);
  dn(q, read(), 1) {
    int x, y;
    read2(x, y);
    x = col[x], y = col[y];
    int LCA = lca(x, y);
    c[x] ++ , c[y] ++ , c[fa[LCA]] -- , c[LCA] -- ;
  }
  down(1, -1);
  cout << res;
}