AT_abc264_e [ABC264E] Blackout 2

思路

一道很经典的题，运用了一种叫「时光倒流」的技巧。

「时光倒流」本质上就是将所有删边（或删点）的操作，通过倒序循环求值的方式转化为加边（或加点）。

「时光倒流」具体实现通常伴随着并查集出现，维护一个连通块的某种性质。

首先，我们需要将所有从始至终没有删过的边加入并查集。在这里，我们的并查集不仅仅要维护某个点 $i$ 的祖先 $f_i$，还要维护某个点 $i$ 所在的连通块是否有电，如果有电记作 $st_i = 1$，否则记作 $st_i = 0$；以及某个点 $i$ 所在连通块的大小 $sz_i$。

那么，我们就可以在合并的时候维护这些东西，以及答案。假设当前我们要合并 $x,y$ 所在的连通块。我们可以先找到它们的祖先，记作 $a,b$，不难发现，如果合并两个连通块会对答案产生贡献，当且仅当其中有一个连通块有电，另一个没电，分类讨论即可。

1. $st_a = 0,st_b = 1$，说明在合并两个连通块后，$x$ 所在联通块中的所有节点都将变为有电，所以，我们可以将 $st_a \leftarrow 1,ans \leftarrow ans + sz_a$。
2. $st_a = 1,st_b = 0$，同理，将 $st_b \leftarrow 1,ans \leftarrow ans + sz_b$。

最后维护一下 $sz$ 和 $f$ 值的变化即可。

Code

#include <bits/stdc++.h>  
#define fst first  
#define snd second  
#define re register  
  
using namespace std;  
  
typedef pair<int,int> pii;  
const int N = 5e5 + 10;  
int n,m,e,q,sum;  
int f[N],sz[N],del[N],ans[N];  
bool st[N],vis[N];  
pii g[N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 3) + (r << 1) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline int find(int x){  
    if (f[x] != x) return f[x] = find(f[x]);  
    return f[x];  
}  
  
inline void merge(int x,int y){  
    int a = find(x);  
    int b = find(y);  
    if (!st[a] && st[b]){  
        st[a] = true;  
        sum += sz[a];  
    }  
    else if (st[a] && !st[b]){  
        st[b] = true;  
        sum += sz[b];  
    }  
    if (a == b) return;  
    f[a] = b;  
    sz[b] += sz[a];  
}  
  
int main(){  
    n = read();  
    m = read();  
    e = read();  
    for (re int i = 1;i <= e;i++){  
        g[i].fst = read();  
        g[i].snd = read();  
    }  
    for (re int i = 1;i <= n;i++) sz[i] = 1;  
    for (re int i = 1;i <= n + m;i++) f[i] = i;  
    for (re int i = n + 1;i <= n + m;i++) st[i] = true;//所有发电站都是有电的   
    q = read();  
    for (re int i = 1;i <= q;i++){  
        del[i] = read();  
        vis[del[i]] = true;  
    }  
    for (re int i = 1;i <= e;i++){  
        if (!vis[i]) merge(g[i].fst,g[i].snd);  
    }  
    for (re int i = q;i;i--){  
        ans[i] = sum;  
        merge(g[del[i]].fst,g[del[i]].snd);  
    }  
    for (re int i = 1;i <= q;i++) printf("%d\n",ans[i]);  
    return 0;  
}