「PA 2014」Fiolki

题目大意：有 $n$ 个瓶子装着 $n$ 种物质，有 $k$ 个反应，每个反应表示 $1ga$ 和 $1gb$ 反应生成 $2g$ 沉淀，反应优先级为给定顺序，有 $m$ 个操作形如将瓶子 $a$ 中的物质倒入瓶子 $b$ 中（保证 $a,b$ 非空）。求最后生成的沉淀质量。$n,m \leq 2 \times 10^5, k \leq 5 \times 10^5$

考虑每两个物质只会反应一次，因此以反应的时间顺序为第一关键字，优先级为第二关键字排序，依次计算沉淀即可，反应的时间顺序就是重构树上 LCA 的深度，因为 $x$ 与 $y$ 反应的位置就是 $lca(x,y)$。

注意判断 $x$ 与 $y$ 不在一棵重构树上，即所有操作没有使 $x$ 与 $y$ 接触的情况。

#include <cstdio>
#include <algorithm>
 
const int N = 500005;
 
int g[N], id[N], siz[N], dep[N], top[N], fa[N], lson[N], rson[N], f[N];
 
struct Node {
    int x, y, lca, id;
    bool operator < (const Node &rhs) const {
        if (dep[lca] == dep[rhs.lca]) return id < rhs.id;
        return dep[lca] > dep[rhs.lca];
    }
} a[N];
 
int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int find(int x) {
    if (x != f[x]) f[x] = find(f[x]);
    return f[x];
}
void dfs1(int cur, int father, int deep) {
    dep[cur] = deep, fa[cur] = father;
    if (lson[cur]) dfs1(lson[cur], cur, deep + 1);
    if (rson[cur]) dfs1(rson[cur], cur, deep + 1);
    siz[cur] = siz[lson[cur]] + siz[rson[cur]] + 1;
}
void dfs2(int cur, int tp) {
    if (!cur) return; top[cur] = tp;
    if (siz[lson[cur]] > siz[rson[cur]])
        dfs2(lson[cur], tp), dfs2(rson[cur], rson[cur]);
    else dfs2(rson[cur], tp), dfs2(lson[cur], lson[cur]);
}
int get_lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]]) x = fa[top[x]];
        else y = fa[top[y]];
    }
    if (dep[x] < dep[y]) return x; return y;
}
 
int main() {
    int n = read(), m = read(), k = read(), cnt = n;
    for (int i = 1; i <= n; ++i) g[i] = read(), id[i] = f[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x = read(), y = read();
        lson[++cnt] = id[x], rson[cnt] = id[y];
        f[id[x]] = f[id[y]] = f[cnt] = cnt, id[y] = cnt;
    }
    for (int i = 1; i <= cnt; ++i)
        if (f[i] == i) dfs1(i, 0, 0), dfs2(i, i);
    for (int i = 1; i <= k; ++i) {
        a[i].x = read(), a[i].y = read(), a[i].id = i;
        if (find(a[i].x) == find(a[i].y)) a[i].lca = get_lca(a[i].x, a[i].y);
    }
    std::sort(a + 1, a + k + 1);
    long long ans = 0;
    for (int i = 1; i <= k; ++i) {
        if (!a[i].lca) continue;
        if (g[a[i].x] > g[a[i].y]) ans += g[a[i].y], g[a[i].x] -= g[a[i].y], g[a[i].y] = 0;
        else ans += g[a[i].x], g[a[i].y] -= g[a[i].x], g[a[i].x] = 0;
    }
    printf("%lld\n", ans << 1);
    return 0;
}

时间复杂度 $O(k \log k)$