[PA2014]Fiolki
题目大意：
有(n(nle2 imes10^5))种不同的液体物质和(n)个容量无限的药瓶。初始时，第(i)个瓶内装着(g_i)克第(i)种液体。(m(mle2 imes10^5))次操作，第(i)个操作是将第(a_i)个瓶子内的所有液体倒入第(b_i)个瓶子，此后第(a_i)个瓶子不会再被用到。
其中，有(k(kle5 imes10^5))对液体物质在一起时会发生反应产生沉淀，具体反应是(1)克(c_i)物质和(1)克(d_i)物质生成(2)克沉淀，直到某一反应物耗尽。沉淀不会和任何物质反应。当有多于一对可以发生反应的物质在一起时，按照给定的顺序进行。每次会等到反应结束后再执行下一步骤。
求总共产生多少沉淀。
思路：
将容器视作结点，每次操作后的容器视作新的结点，操作前容器向操作后的容器连边，最后形成了一个森林。
找到每次反应的LCA，深度大的反应先发生。因此根据反应的顺序进行模拟即可。
源代码：
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=4e5+1,logN=19,K=5e5;
int tot,g[N],dep[N],anc[N][logN],top[N];
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
anc[v][0]=u;
e[u].push_back(v);
}
inline int lg2(const float &x) {
return ((unsigned&)x>>23&255)-127;
}
void dfs(const int &x,const int &par) {
dep[x]=dep[par]+1;
for(register int i=1;i<=lg2(dep[x]);i++) {
anc[x][i]=anc[anc[x][i-1]][i-1];
}
for(unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==par) continue;
dfs(y,x);
}
}
inline int lca(int x,int y) {
if(dep[x]<dep[y]) std::swap(x,y);
for(register int i=lg2(dep[x]-dep[y]);i>=0;i--) {
if(dep[anc[x][i]]>=dep[y]) {
x=anc[x][i];
}
}
for(register int i=lg2(dep[x]);i>=0;i--) {
if(anc[x][i]!=anc[y][i]) {
x=anc[x][i];
y=anc[y][i];
}
}
return x==y?x:anc[x][0];
}
struct Reaction {
int a,b,d,id;
bool operator < (const Reaction &rhs) const {
if(d==rhs.d) return id<rhs.id;
return d>rhs.d;
}
};
Reaction r[K];
int main() {
const int n=tot=getint(),m=getint(),k=getint();
for(register int i=1;i<=n;i++) {
g[i]=getint();
top[i]=i;
}
for(register int i=0;i<m;i++) {
const int u=getint(),v=getint();
tot++;
add_edge(tot,top[u]);
add_edge(tot,top[v]);
top[v]=tot;
}
for(register int i=1;i<=tot;i++) {
if(!anc[i][0]) dfs(i,0);
}
for(register int i=0;i<k;i++) {
r[i].a=getint();
r[i].b=getint();
r[i].d=dep[lca(r[i].a,r[i].b)];
r[i].id=i;
}
std::sort(&r[0],&r[k]);
int64 ans=0;
for(register int i=0;i<k;i++) {
if(!r[i].d) continue;
const int tmp=std::min(g[r[i].a],g[r[i].b]);
g[r[i].a]-=tmp;
g[r[i].b]-=tmp;
ans+=tmp*2;
}
printf("%lld
",ans);
return 0;
}