题目解析
神奇题目，洛谷评分居然是普及+，果然还是我太菜了吗(qwq)
题意我也看了好一会儿，我以为它是一个类似于化合反应的东西，把试剂(a)倒入试剂(b)之后，药水就全部变成试剂(b)了，而质量为两者的和（质量守恒定律）。
但实际上题目的意思只是把这两种药水混合在一起，是物理变化，只有生成的那个沉淀是化学变化。
首先可以想到一个(O(mk))的大暴力，但是数据范围显然过不去。
考虑到重要的是这些沉淀们各自的顺序，因为顺序不同，发生反应时反应物的已消耗量可能不同，也就是反应物的量可能不同，产物的量可能不同。
所以重点在于判断各个沉淀的顺序。
神奇的做法来喏，就是其实把两个反应物向生成物连一条边（我刚开始想的是直接(a->b)连边了，没有想到把(b)自己拆成反应物和生成物，然后没有做出来），那么就形成了一个二叉树森林（不一定联通），叶子结点都是原来的试剂，如果两种试剂会反应，那么它们会在(lca)的位置相遇，然后反应生成沉淀，生成的沉淀质量为(2)倍较小质量数，然后各自减去这个转化量。
显然(lca)深度比较大沉淀先发生，于是我们就找出了这些沉淀的顺序。注意(lca)深度相同时，要按照给出顺序排，题目说了按照反应优先顺序给出这(k)对可以反应的物质。
用倍增求(lcs)，时间复杂度应该为(O(k imes log(n+m)))
►Code View
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define N 200005
#define M 200005
#define K 500005
#define INF 0x3f3f3f3f
#define LL long long
int rd()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f*x;
}
int n,m,k;
int g[N];
vector<int>G[N+M];
int pos[N];//当前试剂i的结点编号
int f[N+M][25],dep[N+M];
struct node{
int a,b,cd,id;
}q[K];
int cnt;//有效沉淀反应个数
LL ans;
void add(int u,int v)
{
G[v].push_back(u);
}
bool cmp(node p,node q)
{
if(p.cd==q.cd) return p.id<q.id;//注意k对试剂按照反应优先顺序给出
//我刚开始以为同一层的顺序可以随便 实际上不行 因为试剂有量的多少
return p.cd>q.cd;
}
void dfs(int u)
{
for(int i=1;i<=20;i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==f[u][0]) continue;
f[v][0]=u;
dep[v]=dep[u]+1;
dfs(v);
}
}
int LCA(int u,int v)
{
int tmp;
if(dep[u]<dep[v]) tmp=u,u=v,v=tmp;
for(int j=20;j>=0;j--)
if(dep[f[u][j]]>=dep[v])
u=f[u][j];
if(u==v) return u;
for(int j=20;j>=0;j--)
if(f[u][j]!=f[v][j])
u=f[u][j],v=f[v][j];
return f[u][0];
}
int main()
{
n=rd(),m=rd(),k=rd();
for(int i=1;i<=n;i++)
{
pos[i]=i;
g[i]=rd();
}
for(int i=1;i<=m;i++)
{
int a=rd(),b=rd();
add(pos[a],n+i);
add(pos[b],n+i);
pos[b]=n+i;
}
for(int i=n+m;i>=1;i--)
if(f[i][0]==0)//可能不连通 即二叉树森林
dfs(i);
for(int i=1;i<=k;i++)
{
int a=rd(),b=rd(),lca=LCA(a,b);
if(!lca) continue;//这对沉淀不会出现
node tmp; tmp.a=a,tmp.b=b,tmp.cd=dep[lca],tmp.id=i;
q[++cnt]=tmp;
}
sort(q+1,q+cnt+1,cmp);
for(int i=1;i<=cnt;i++)
{
int del=min(g[q[i].a],g[q[i].b]);
g[q[i].a]-=del,g[q[i].b]-=del;
ans=ans+2ll*del;
}
printf("%lld
",ans);
return 0;
}