[PA2014]Fiolki

LCA 图论

题面

吉丽有$n$种不同的液体物质，和$n$个药瓶（均从1到n编号）。吉丽需要执行一定的$k$步骤来配置药水，步骤是将某个瓶子内的所有液体倒入另一个瓶子。
吉丽知道某$m$对液体物质在一起时会发生反应产生沉淀。生成的沉淀不会和任何物质反应。当有多于一对可以发生反应的物质在一起时，吉丽知道它们的反应顺序。每次倾倒完后，吉丽会等到反应结束后再执行下一步骤。吉丽想知道配置过程中总共产生多少沉淀。

• $m,n\leq2*10^5,k\leq5*10^5$

解析

这题真是脑洞神题
发现模拟妥妥的$O(mk)$。
记得约束关系一般都能牵扯到图论。（然后我就懵了）
实际上，这种化学反应（化合反应）很容易让我们想起树形结构。

于是一切都自然了。
我们把生成物作为一对反应物的父亲，反应完就把反应物的位置改到生成物那儿。
这样能构成森林。（图不一定联通）
显然深度越大，反应顺序越靠前的越先反应。
按此顺序，通过找$lca$得到生成物，一一模拟即可。
复杂度$O(klogn)$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
struct Edge{int to,nxt;}e[N<<1];
struct dat{int u,v,lca,deep,id;bool operator < (const dat &o) const{return (deep>o.deep)||(deep==o.deep&&id<o.id);}}a[N<<1];
int n,g[N],tot,m,k,cnt,h[N],ff,d[N],sz[N],son[N],f[N],top[N],pos[N];
ll ans;
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;e[++cnt]=(Edge){u,h[v]};h[v]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void dfs1(re int u,re int fa)
{
  d[u]=d[fa]+1;f[u]=fa;sz[u]=1;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs1(v,u);
      sz[u]+=sz[v];
      if(sz[son[u]]<sz[v]) son[u]=v;
    }
}
il void dfs2(re int u,re int up)
{
  top[u]=up;
  if(son[u]) dfs2(son[u],up);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==f[u]||v==son[u]) continue;
      dfs2(v,v);
    }
}
il int getlca(re int u,re int v)
{
  while(top[u]^top[v])
    {
      if(d[top[u]]<d[top[v]]) swap(u,v);
      u=f[top[u]];
    }
  return d[u]<d[v]?u:v;
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();m=gi();k=gi();
  fp(i,1,n) pos[i]=i,g[i]=gi();
  fp(i,1,m)
    {
      re int u=gi(),v=gi(),ff=n+i;
      add(pos[u],ff);add(pos[v],ff);pos[v]=ff;
    }
  fq(i,n+m,1) if(!f[i]) dfs1(i,0),dfs2(i,i);
  fp(i,1,k)
  {
    re int u=gi(),v=gi(),lca=getlca(u,v);
    if(!lca) continue;//不反应
    a[++tot]=(dat){u,v,lca,d[lca],i};
  }
  sort(a+1,a+1+tot);
  fp(i,1,tot)
    {
      re int u=a[i].u,v=a[i].v,gg=min(g[u],g[v]);
      g[u]-=gg;g[v]-=gg;ans+=gg*2;
    }
    printf("%lld\n",ans);
  return 0;
}