P11674 [USACO25JAN] Reachable Pairs G

· · 题解

显然正面直接并查集模拟，由于普及组算法无法处理分裂，所以排除，正难则反，倒着做就是合并所以考虑倒过来。

若只有操作 1:~ 此时，我们只需要正遍历每个点，把与自己相邻的所有没删的点记录下来，再倒着做。加一个点合并一群并查集并更新答案。

现在想操作 2:~ 显然不能暴力删加边。注意到删了这个点，不会改变连通性，没被删的点能到达的点除了这个被删的没有变化。所以我们可以想能不能做一个伪删除。

于是， 2 操作我们只在这点上打标记，作为虚点，在正遍历时，把虚点视作永远存活，即不管当前点删在它之前还是之后，只要遍历到虚点就连它。

但倒着遍历也不能直接遍历到虚点就遍历他的所有点，所以我们提前处理他的影响，他连的实点不用管，在实点加入进来时合并就行，他连的虚点就提前加入一个并查集，这样复杂度正确且把点之间的关系都处理好了。

需要注意，虚点合并不能计算贡献，我们可以提前把虚点的 size 设为 0 ，在加入虚点时直接把他所在连通块的 size+1 就行。

非虚点加入方式同只有操作 1 时没有变化，见代码：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
#define MAXM 800010
#define ll long long
int Next[MAXM],edge[MAXM],size[MAXN];
int head[MAXN],vis[MAXN],mk[MAXN];
int n,m,tot,fa[MAXN];
ll ans[MAXN],now;
char s[MAXN];
vector<int>p[MAXN],q[MAXN];
void add(int x,int y)
{
    edge[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void join(int x,int y)
{
    int f1=find(x),f2=find(y);
    if(f1!=f2){
        now+=1ll*size[f1]*size[f2];
        size[f2]+=size[f1],fa[f1]=f2;
    }
}
void solve(int x)
{
    for(int i=0;i<q[x].size();i++)
    {
        int y=q[x][i];
        join(x,y);
        if(!vis[y]&&mk[i]){
            vis[y]=1;
            solve(y);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    cin>>(s+1);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++)
        fa[i]=i,size[i]=1;
    for(int i=1;i<=n;i++)
    {
        mk[i]=s[i]-'0';
        if(mk[i])size[i]--;
        for(int j=head[i];j;j=Next[j])
        {
            int v=edge[j];
            if(v>i||mk[v])p[i].push_back(v);
            if(mk[v]&&mk[i])
                join(v,i);
        }
    }
    for(int i=n;i>=1;i--)
    {
        d[i]=1;
        if(mk[i]){
            now+=size[find(i)]++;
            ans[i]=now;
            if(vis[i])continue;
            vis[i]=1;
        }
        for(int j=0;j<p[i].size();j++)
            join(p[i][j],i);
        ans[i]=now;
    }
    for(int i=1;i<=n;i++)
        printf("%lld\n",ans[i]);
    return 0;
}