P6351 [PA2011] Hard Choice 题解

· · 题解

早早地写出了全线性做法，因为要放模拟赛没挂题解。确定性线性做法最早于我于 2024.8.12 提出。

先以每条边被删除的时间从后到前的顺序建出最小生成树，对于一个询问 (u,v)，把所有没被删的边在生成树上做链覆盖，若 u,v 之间所有的树边都被覆盖 \ge 2 次，那么 u,v 之间有两条边完全不同的路径。

简单证明一下，因为是最小生成树，如果有树边没覆盖，那 u,v 之间根本就不连通；如果有树边被覆盖仅 1 次，那不可能是非树边覆盖到了它，只能是它自己覆盖了自己，否则可以调整说明最小生成树不合法，此时该边称为瓶颈，不存在两条边完全不同路径；否则 u,v 之间一定由若干环拼成，一定可以找到两条边完全不同的路径。

到这里，有一个最朴素的 O(n\log^2 n) 的做法，即求出最小生成树后，树剖一下，线段树维护区间加，区间最小值，每次暴力覆盖和询问。

但是上面的做法是没有什么前途的，注意到我们做链覆盖和链查询，最后只是为了比较链上最小覆盖次数与 2 之间的大小关系，用这些数据结构很浪费。

换一种思考方式，该问题等价于我们倒着做，每一条边的存在时间是一段后缀，每次用边去做链覆盖时，如果一条树边被覆盖次数达到 2，就在新图上加入，询问等价于查询 u,v 之间是否连通。而这些都可以用一个并查集去维护，并查集维护树上覆盖次数 \ge 2 的边的连通块，每次覆盖暴力向上跳连通块，恰使得一条边达到 2 时就把并查集缩起来，询问也只需在这个并查集上查询即可。

因为每条边最多只被覆盖 2 次，因此后面这些复杂度是 O(n)。前面的最小生成树不需要排序，先考虑加入没被删除的边，然后按照删除顺序依次考虑加入即可。总复杂度 O(n)，最优解遥遥领先。由于 vector 常数较大，建议手写链表。

这个题很不爽的是给删除的边是以端点给出的，还要写哈希或者 umap。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

int n,m,q,tm,cnt;
int f[2000005];
int h[2000005];
int hd[2000005];
int fa[2000005];
int it[2000005];
int dep[2000005];
int dfn[2000005];
int out[2000005];
bool del[2000005];
struct node{int op,x,y;};
node e[2000005];
node g[2000005];
node opt[2000005];
bool ans[2000005];
unordered_map <long long,int> mp;

inline void add(int u,int v,int id){
    g[++cnt]={v,hd[u],id},hd[u]=cnt;
    g[++cnt]={u,hd[v],id},hd[v]=cnt;
    return ;
}

inline void in(int &n){
    n=0;
    char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
    return ;
}

inline int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}

inline void dfs(int u,int f){
    fa[u]=f;
    dep[u]=dep[f]+1;
    dfn[u]=++tm;
    for(int i=hd[u];i;i=g[i].x){
        int v=g[i].op,id=g[i].y;
        if(v==f) continue;
        it[v]=id;
        dfs(v,u);
    }
    out[u]=tm;
    return ;
}

inline void Cover(int u,int v){
    int l=min(dfn[u],dfn[v]),r=max(dfn[u],dfn[v]);
    int pos=Find(u);
    while(dfn[pos]>l||out[pos]<r){
        h[it[pos]]++;
        if(h[it[pos]]==2) f[pos]=Find(fa[pos]);
        pos=Find(fa[pos]);
    }
    pos=Find(v);
    while(dfn[pos]>l||out[pos]<r){
        h[it[pos]]++;
        if(h[it[pos]]==2) f[pos]=Find(fa[pos]);
        pos=Find(fa[pos]);
    }
    return ;
}

int main(){
    in(n),in(m),in(q);
    for(int i=1;i<=m;i++){
        int u,v;
        in(u),in(v);
        mp[1ll*min(u,v)*n+max(u,v)]=i;
        e[i]={1,u,v};
    }
    for(int i=1;i<=q;i++){
        char c[3];
        scanf("%s",c+1);
        if(c[1]=='Z'){
            int u,v;
            in(u),in(v);
            u=mp[1ll*min(u,v)*n+max(u,v)];
            del[u]=1;
            opt[i]=e[u];
        }
        else{
            int u,v;
            in(u),in(v);
            opt[i]={2,u,v};
        }
    }
    int tt=0;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        if(del[i]) continue;
        int u=Find(e[i].x),v=Find(e[i].y);
        if(u!=v){
            f[u]=v;
            add(e[i].x,e[i].y,++tt);
        }
    }
    for(int i=q;i>=1;i--)
        if(opt[i].op==1){
            int u=Find(opt[i].x),v=Find(opt[i].y);
            if(u!=v){
                f[u]=v;
                add(opt[i].x,opt[i].y,++tt);
            }
        }
    for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,0);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) if(!del[i]) Cover(e[i].x,e[i].y);
    tt=0;
    for(int i=q;i>=1;i--){
        if(opt[i].op==1) Cover(opt[i].x,opt[i].y);
        else ans[++tt]=(Find(opt[i].x)==Find(opt[i].y));
    }
    for(int i=tt;i>=1;i--) puts(ans[i]?"TAK":"NIE");

    return 0;
}