BZOJ3712[PA2014]Fiolki——并查集重构树

题目描述

化学家吉丽想要配置一种神奇的药水来拯救世界。
吉丽有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

样例输出

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);
}