30分RE求条

#include "bits/stdc++.h"
using namespace std;
const int N = 5e5 + 5, M = 2e6 + 5;
int n, m, a[N], stk[N], top, low[N], dfn[N], cnt, in[N], len, 
w[N], st[25][N], fa[N], lg[N], di[N], q, ans;
bool vis[M];
struct node {
	int x, y;
};
vector <node> e[N];
vector <int> te[N];
void tarjan (int x) {
	low[x] = dfn[x] = ++cnt;
	stk[++top] = x;
	for (node i : e[x]) {
		int v = i.x, id = i.y;
		if (vis[id]) continue;
		vis[id] = 1;
		if (!dfn[v]) tarjan (v);
		low[x] = min (low[x], low[v]);//这个写法虽然不正规，但是在求边双和强连通是可以用的，可以通过模板题。（写习惯了）
	}
	if (low[x] == dfn[x]) {
		++len;
		while (stk[top + 1] != x) {
			in[stk[top]] = len;
			w[len] += a[stk[top]];
			top--;
		}
	}
}
void dfs (int x, int f) {
	st[0][dfn[x] = ++cnt] = f;
	fa[x] = f;
	for (int v : te[x]) {
		if (v != f) dfs (v, x);
	}
}
int qmn (int x, int y) {
	return dfn[x] < dfn[y] ? x : y;
}
int lca (int u, int v) {
	if (u == v) return u;
	if ((u = dfn[u]) > (v = dfn[v])) swap (u, v);
	int x = lg[v - u++];
	return qmn (st[u][x], st[v - (1 << x) + 1][x]);
}
void dfss (int x, int fa) {
	for (int v : te[x]) {
		if (v != fa) {
			dfss (v, x);
			di[x] += di[v];
		}
	}
}
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); //被卡常后听说能加速。
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		e[u].push_back ({v, i});
		e[v].push_back ({u, i});
	}
	tarjan (1);
	memset (vis, true, sizeof (vis));
	for (int i = 1; i <= n; i++) {
		lg[i + 1] = lg[i + 1 >> 1] + 1;
		for (node j : e[i]) {
			int u = in[i], v = in[j.x];
			if (vis[v] && u != v) {
				vis[v] = false;
				te[u].push_back (v);
			}
		}
		for (int v : te[i]) vis[v] = true;
	}
	cnt = 0;
	dfs (1, 0);
	for (int i = 1; i <= lg[len]; i++) {
		for (int j = 1; j + (1 << i) - 1 <= len; j++) {
			st[i][j] = qmn (st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
		}
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int x, y, z;
		cin >> x >> y;
		x = in[x], y = in[y];
		z = lca (x, y);
		di[x]++; di[y]++; di[fa[z]] -= 2;
	}
	dfss (1, 0);
	for (int i = 1; i <= len; i++) {
		if (di[i]) {
			ans += w[i];
		}
	}
	cout << ans << endl;
	return 0;
}