BZOJ3712 [PA2014] Filoki

2018 年 12 月 26 日发布.

Description

有若干药瓶，第 $i$ 号药瓶里装着 $g_i$ 克 $i$ 号物质。

有 $m$ 次操作，第 $i$ 次会把 $a_i$ 号瓶子全部倒入 $b_i$ 号瓶子，之后 $a_i$ 号瓶子不会再用到。

一共 $k$ 对物质之间会反应生成沉淀（沉淀不再参与反应），1 克 $c_i$ 物质和 1 克 $d_i$ 物质反应生成 2 克沉淀。

当有若干反应都可以进行的时候优先进行编号小的反应。求整个过程中一共生成了多少沉淀。

$m<n\leqslant2\times10^5,k\leqslant5\times10^5$。

Solution

如果把 $a_i$ 瓶子倒入 $b_i$ 瓶子，那么新建一个结点作为 $a_i$ 和 $b_i$ 的父亲，将它作为新的 $b_i$ 瓶子对应的结点。

这样的话相当于每个结点的物质是两个儿子的物质合起来，并进行反应。

显然第 $i$ 种反应只可能会在 ${\rm LCA}(c_i,d_i)$ 处反应。

我们假设所有物质最开始都是放在一起的，但是不发生反应。

把这个森林按照后序遍历，遍历到某个结点的时候再让它上面的反应依次进行。

复杂度 $O(m+(n+k)\log n)$。

代码中因为每个点父亲编号都比它大所以直接按结点顺序从前往后进行反应即可。

Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>

const int N = 400050;
const int M = 500050;

typedef long long LL;

int n, m, g[N], lc[N], rc[N], now[N];
int dep[N], fa[N][20];
int k, c[N], L[M], a[M], b[M], T[M];

int LCA(int x, int y) {
  if (dep[x] < dep[y]) std::swap(x, y);
  for (int i = 19; ~i; --i)
    if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
  if (x == y) return x;
  for (int i = 19; ~i; --i)
    if (fa[x][i] != fa[y][i]) {
      x = fa[x][i];
      y = fa[y][i];
    }
  return fa[x][0];
}

int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &g[now[i] = i]);
  for (int i = 1, x, y; i <= m; ++i) {
    scanf("%d%d", &x, &y);
    fa[lc[i + n] = now[x]][0] = i + n;
    fa[rc[i + n] = now[y]][0] = i + n;
    now[y] = i + n;
  }
  for (int x = n + m; x; --x) {
    if (!fa[x][0]) fa[x][0] = n + m + 1;
    dep[x] = dep[fa[x][0]] + 1;
    for (int i = 0; fa[x][i]; ++i)
      fa[x][i + 1] = fa[fa[x][i]][i];
  }
  for (int i = 1; i <= k; ++i) {
    scanf("%d%d", &a[i], &b[i]);
    ++c[L[i] = LCA(a[i], b[i])];
  }
  for (int i = 1; i <= n + m + 1; ++i) c[i] += c[i - 1];
  for (int i = k; i; --i) T[c[L[i]]--] = i;
  LL ans = 0;
  for (int i = 1; i <= k && L[T[i]] <= n + m; ++i) {
    int x = T[i], t = std::min(g[a[x]], g[b[x]]);
    ans += 2 * t;
    g[a[x]] -= t;
    g[b[x]] -= t;
  }
  printf("%lld\n", ans);
  return 0;
}