Description：

有 $n$ 种化学物质装在不同的瓶子，第 $i$ 种物质有 $m_i$ 。有 $m$ 种反应，两个物质接触时会以 $1$ 比 $1$ 反应生成沉淀，反应的优先级和输入顺序相同，按顺序执行 $q$ 个步骤，将第 $a$ 个瓶子的液体倒入第 $b$ 个瓶子中，求生成的沉淀。

$1\leqslant n\leqslant 10^6$

Solution：

首先直接每次计算这一次操作产生了多少沉淀是肯定不行的，于是考虑对于每种反应，它对答案的贡献是多少。

首先某个反应一定只会发生一次，并且发生在两个物质第一次接触的时候，那么我们就可以建出一棵克鲁斯卡尔重构树，然后反应一定在 $LCA$ 处发生，然后我们对每个反应预处理发生的位置，然后按深度为第一关键字优先级为第二关键字依次反应统计答案就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

} 

int n,m,p;

#define MAXN 400010

#define MAXQ 500010

int s[MAXN];

int f[MAXN];

int find(int x){return (f[x] == 0 ? x : f[x] = find(f[x]));}

struct edges

{

	int a,b;

}es[MAXN];

int tot;

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int dep[MAXN],top[MAXN],son[MAXN],siz[MAXN],fa[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		fa[e[i].to] = k;

		dfs1(e[i].to,depth + 1);

		siz[k] += siz[e[i].to];

		if(son[k] == 0 || siz[e[i].to] > siz[son[k]])son[k] = e[i].to;

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k] || e[i].to == son[k])continue;

		dfs2(e[i].to,e[i].to);

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

struct query

{

	int a,b,w,id;

}q[MAXQ];

long long ans = 0;

bool cmp(query a,query b){return a.w == b.w ? a.id < b.id : a.w > b.w;}

int main()

{

	scanf("%d%d%d",&n,&m,&p);

	for(int i = 1;i <= n;++i)s[i] = rd();

	for(int i = 1;i <= m;++i)

	{

		es[i].a = rd();es[i].b = rd();

	}

	tot = n;

	for(int i = 1;i <= m;++i)

	{

		if(find(es[i].a) == find(es[i].b))continue;

		++tot;

		add(tot,find(es[i].a));add(tot,find(es[i].b));

		f[find(es[i].a)] = tot;f[find(es[i].b)] = tot;

	}

	for(int i = tot;i >= 1;--i)

	{

		if(dep[i] == 0)dfs1(i,i),dfs2(i,i);

	}

	for(int i = 1;i <= p;++i)

	{

		q[i].a = rd();q[i].b = rd();

		if(find(q[i].a) != find(q[i].b))q[i].w = 0x3f3f3f3f;

		else q[i].w = dep[LCA(q[i].a,q[i].b)];

		q[i].id = i;

	}

	sort(q + 1,q + 1 + p,cmp);

	for(int i = 1;i <= p;++i)

	{

		if(q[i].w == 0x3f3f3f3f)continue;

		int v = min(s[q[i].a],s[q[i].b]);

		ans += v * 2;s[q[i].a] -= v;s[q[i].b] -= v;

	}

	cout << ans << endl;

	return 0;

}