自动搬运

查看原文

来自洛谷，原作者为

	Reunite Wish us good luck.

搬运于2025-08-24 22:19:57，当前版本为作者最后更新于2024-09-24 14:53:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

早早地写出了全线性做法，因为要放模拟赛没挂题解。确定性线性做法最早于我于 $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;
}