题目描述
化学家吉丽想要配置一种神奇的药水来拯救世界。
吉丽有n种不同的液体物质，和n个药瓶（均从1到n编号）。初始时，第i个瓶内装着g[i]克的第i种物质。吉丽需要执行一定的步骤来配置药水，第i个步骤是将第a[i]个瓶子内的所有液体倒入第b[i]个瓶子，此后第a[i]个瓶子不会再被用到。瓶子的容量可以视作是无限的。
吉丽知道某几对液体物质在一起时会发生反应产生沉淀，具体反应是1克c[i]物质和1克d[i]物质生成2克沉淀，一直进行直到某一反应物耗尽。生成的沉淀不会和任何物质反应。当有多于一对可以发生反应的物质在一起时，吉丽知道它们的反应顺序。每次倾倒完后，吉丽会等到反应结束后再执行下一步骤。
吉丽想知道配置过程中总共产生多少沉淀。
输入
第一行三个整数n,m,k(0<=m<n<=200000,0<=k<=500000)，分别表示药瓶的个数（即物质的种数），操作步数，可以发生的反应数量。
第二行有n个整数g[1],g[2],…,g[n]（1<=g[i]<=10^9)，表示初始时每个瓶内物质的质量。
接下来m行，每行两个整数a[i],b[i](1<=a[i],b[i]<=n,a[i]≠b[i])，表示第i个步骤。保证a[i]在以后的步骤中不再出现。
接下来k行，每行是一对可以发生反应的物质c[i],d[i](1<=c[i],d[i]<=n,c[i]≠d[i])，按照反应的优先顺序给出。同一个反应不会重复出现。
输出
样例输入
3 2 1
2 3 4
1 2
3 2
2 3
2 3 4
1 2
3 2
2 3
样例输出
6
我们将每瓶药看成一个节点，对于一个操作合并x,y两瓶药就再新建一个节点代表这个操作，左右子节点分别是x,y两瓶药所在子树的根节点。
这样像kruskal重构树一样建出一棵二叉树，也叫并查集重构树。
可以发现对于每一对反应的两瓶药x,y，都是在它们在并查集重构树上的LCA处那个操作时发生反应的。
我们以每个反应的LCA深度为第一关键字，优先度为第二关键字排序，然后模拟一下即可。
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,m,k;
int g[200010];
int fa[400010];
int vis[400010];
ll ans;
int f[400010][20];
int d[400010];
int cnt;
int tot;
int ls[400010];
int rs[400010];
struct miku
{
int dep;
int pos;
int x,y;
}a[500010];
int x,y;
int find(int x)
{
if(fa[x]==x)
{
return x;
}
return fa[x]=find(fa[x]);
}
bool cmp(miku a,miku b)
{
if(a.dep!=b.dep)
{
return a.dep>b.dep;
}
return a.pos<b.pos;
}
void dfs(int x)
{
d[x]=d[f[x][0]]+1;
for(int i=1;i<=18;i++)
{
f[x][i]=f[f[x][i-1]][i-1];
}
if(ls[x])
{
dfs(ls[x]);
}
if(rs[x])
{
dfs(rs[x]);
}
}
int lca(int x,int y)
{
if(d[x]<d[y])
{
swap(x,y);
}
int dep=d[x]-d[y];
for(int i=0;i<=18;i++)
{
if((dep&(1<<i)))
{
x=f[x][i];
}
}
if(x==y)
{
return x;
}
for(int i=18;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&g[i]);
}
for(int i=1;i<=2*n;i++)
{
fa[i]=i;
}
cnt=n;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
int fx=find(x);
int fy=find(y);
cnt++;
f[fx][0]=cnt;
f[fy][0]=cnt;
fa[fx]=cnt;
fa[fy]=cnt;
ls[cnt]=fx;
rs[cnt]=fy;
}
for(int i=1;i<=n;i++)
{
int rt=find(i);
if(!vis[rt])
{
vis[rt]=1;
dfs(rt);
}
}
for(int i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
if(find(x)==find(y))
{
a[++tot].dep=d[lca(x,y)];
a[tot].pos=i;
a[tot].x=x;
a[tot].y=y;
}
}
sort(a+1,a+1+tot,cmp);
for(int i=1;i<=tot;i++)
{
int s=g[a[i].x];
int t=g[a[i].y];
if(s>t)
{
swap(s,t);
}
ans+=2ll*s;
g[a[i].x]-=s;
g[a[i].y]-=s;
}
printf("%lld",ans);
}