套路题+裸题

首先肯定离线，倒过来处理，删边->加边

连边的时候，如果不连通就连，否则在这两个点的链上打个覆盖标记，查询的时候输出没被覆盖的路径条数

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;#define rg register#define vd void#define sta static#define il inlineil int gi(){    rg int x=0,f=1;rg char ch=getchar();    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();    return x*f;}const int maxn=30001,maxm=100001,maxq=40001;int FA[maxn];il int Find(int x){return x==FA[x]?x:FA[x]=Find(FA[x]);}int ans[maxm],n,m,q;int ch[maxn<<1][2],fa[maxn<<1],sum[maxn<<1],idx;bool rev[maxn<<1],tag[maxn<<1],yes[maxn<<1];int opt[maxq],qa[maxq],qb[maxq];typedef const int& ci;il bool isrt(ci x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}il vd upd(ci x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+yes[x];}il vd Rev(ci x){rev[x]^=1,swap(ch[x][0],ch[x][1]);}il vd Cover(ci x){tag[x]=1,yes[x]=0,sum[x]=0;}il vd down(ci x){    if(!isrt(x))down(fa[x]);    if(rev[x])Rev(ch[x][0]),Rev(ch[x][1]),rev[x]=0;    if(tag[x])Cover(ch[x][0]),Cover(ch[x][1]),tag[x]=0;}il vd rotate(ci x){    sta int y,z,o;y=fa[x],z=fa[y],o=x==ch[y][1];    if(!isrt(y))ch[z][ch[z][1]==y]=x;fa[x]=z;    ch[y][o]=ch[x][!o];fa[ch[x][!o]]=y;    fa[y]=x;ch[x][!o]=y;    upd(y);}il vd splay(ci x){    down(x);sta int y,z;    for(y=fa[x],z=fa[y];!isrt(x);rotate(x),y=fa[x],z=fa[y])        if(!isrt(y))rotate(((ch[y][0]==x)^(ch[z][0]==y))?y:x);    upd(x);}il vd access(int x){for(rg int y=0;x;x=fa[y=x])splay(x),ch[x][1]=y,upd(x);}il vd makert(ci x){access(x),splay(x),Rev(x);}il vd link(ci x,ci y){makert(x),fa[x]=y;}il vd split(ci x,ci y){makert(x),access(y),splay(y);}il vd Link(ci x,ci y){    if(Find(x)==Find(y))split(x,y),Cover(y);    else ++idx,yes[idx]=1,sum[idx]=1,link(x,idx),link(y,idx),FA[Find(x)]=Find(y);}set
        
         
           >yyb;main(){ n=gi(),m=gi();idx=n; for(rg int i=1;i<=n;++i)FA[i]=i; int x,y,c; for(rg int i=1;i<=m;++i){ x=gi(),y=gi();if(x>y)swap(x,y); yyb.insert(make_pair(x,y)); } while(c=gi(),~c){ ++q,opt[q]=c,qa[q]=gi(),qb[q]=gi(); if(opt[q]==0){ if(qa[q]>qb[q])swap(qa[q],qb[q]); yyb.erase(yyb.find(make_pair(qa[q],qb[q]))); } } for(set
          
           
             >::iterator it=yyb.begin();it!=yyb.end();++it) Link(it->first,it->second); for(rg int i=q;i;--i) if(opt[i]==0)Link(qa[i],qb[i]); else split(qa[i],qb[i]),ans[++ans[0]]=sum[qb[i]]; while(ans[0])printf("%d\n",ans[ans[0]--]); return 0;}