【分析】
我的做法跟BZOJ 1969大致一样【我改了改代码交的。。
这题没说删完的图联通，所以最后还要处理一下。。
然后每次询问x到y的关键边数量是否为0就好了。
【详细做法见BZOJ 1969
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 100010
#define Maxm 100010 struct node
{
int x,y,next;
int bj,id;
}t[Maxn*],tt[Maxm*];
int first[Maxn],len; void ins(int x,int y)
{
// printf("%d -> %d\n",x,y);
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} struct nnode
{
int l,r,lc,rc,sm;
}tr[Maxn*]; void upd(int x)
{
if(tr[x].l==tr[x].r||tr[x].sm!=) return;
int lc=tr[x].lc,rc=tr[x].rc;
tr[lc].sm=tr[rc].sm=;
} int tot;
int build(int l,int r)
{
int x=++tot;
tr[x].l=l;tr[x].r=r;
if(l!=r)
{
int mid=(l+r)>>;
tr[x].lc=build(l,mid);
tr[x].rc=build(mid+,r);
}
else tr[x].lc=tr[x].rc=;
tr[x].sm=r-l+;
return x;
} void change(int x,int l,int r)
{
if(tr[x].l==l&&tr[x].r==r)
{
tr[x].sm=;
return;
}
upd(x);
int mid=(tr[x].l+tr[x].r)>>,lc=tr[x].lc,rc=tr[x].rc;
if(r<=mid) change(lc,l,r);
else if(l>mid) change(rc,l,r);
else
{
change(lc,l,mid);
change(rc,mid+,r);
}
tr[x].sm=tr[lc].sm+tr[rc].sm;
} int query(int x,int l,int r)
{
if(tr[x].sm==) return ;
if(tr[x].l==l&&tr[x].r==r) return tr[x].sm;
upd(x);
int mid=(tr[x].l+tr[x].r)>>,lc=tr[x].lc,rc=tr[x].rc;
if(r<=mid) return query(lc,l,r);
else if(l>mid) return query(rc,l,r);
else return query(lc,l,mid)+query(rc,mid+,r);
} int tp[Maxn],sum[Maxn],son[Maxn],dfn[Maxn],dep[Maxn];
int ff[Maxn];
int cnt;
void dfs(int x,int f)
{
son[x]=;sum[x]=;dep[x]=dep[f]+;
ff[x]=f;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
{
int y=t[i].y;
dfs(y,x);
sum[x]+=sum[y];
if(son[x]==||sum[son[x]]<sum[y]) son[x]=y;
}
} void dfs2(int x,int tpp)
{
dfn[x]=++cnt;tp[x]=tpp;
if(son[x]) dfs2(son[x],tpp);
for(int i=first[x];i;i=t[i].next) if(t[i].y!=ff[x]&&t[i].y!=son[x])
{
int y=t[i].y;
dfs2(y,y);
}
} void fchange(int x,int y)
{
while(tp[x]!=tp[y])
{
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
change(,dfn[tp[x]],dfn[x]);
x=ff[tp[x]];
}
if(dep[x]<dep[y]) swap(x,y);
if(x!=y) change(,dfn[y]+,dfn[x]);
} int fquery(int x,int y)
{
int ans=;
while(tp[x]!=tp[y])
{
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
ans+=query(,dfn[tp[x]],dfn[x]);
x=ff[tp[x]];
}
if(dep[x]<dep[y]) swap(x,y);
if(x!=y)
{
// if(dfn[y]+1>dfn[x]) while(1);
ans+=query(,dfn[y]+,dfn[x]);
}
return ans;
} int fa[Maxn];
int ffa(int x)
{
if(fa[x]!=x) fa[x]=ffa(fa[x]);
return fa[x];
} bool cmp(node x,node y)
{
if(x.x==y.x&&x.y==y.y) return x.bj<y.bj;
return (x.x==y.x)?(x.y<y.y):(x.x<y.x);
}
bool cmp2(node x,node y) {return x.id<y.id;} int ans[Maxn]; char s[]; void solve()
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
int ll=;
for(int i=;i<=m;i++)
{
int x,y;
ll++;
scanf("%d%d",&tt[ll].x,&tt[ll].y);
if(tt[ll].x>tt[ll].y) swap(tt[ll].x,tt[ll].y);
tt[ll].bj=;//cha ru
}
int ct=;
while(q--)
{
scanf("%s",s);
ll++;
scanf("%d%d",&tt[ll].x,&tt[ll].y);
if(tt[ll].x>tt[ll].y) swap(tt[ll].x,tt[ll].y);
if(s[]=='Z') tt[ll].bj=-;//shan chu
else tt[ll].bj=;//xun wen
tt[ll].id=++ct;
}
sort(tt+,tt++ll,cmp);
for(int i=;i<=n;i++) fa[i]=i;
ct++;
int pp=;
for(int i=;i<=ll;i++)
{
if(tt[i].bj==) continue;
if(tt[i].bj==)
{
if(pp==||tt[i].x!=tt[pp].x||tt[i].y!=tt[pp].y)
{
if(ffa(tt[i].x)==ffa(tt[i].y))
{
tt[i].bj=-;
tt[i].id=ct;
}
else
{
ins(tt[i].x,tt[i].y);
ins(tt[i].y,tt[i].x);
fa[ffa(tt[i].x)]=tt[i].y;
}
}
}
pp=i;
}
sort(tt+,tt++ll,cmp2);
for(int i=ll;i>=;i--) if(tt[i].bj==-)
{
if(ffa(tt[i].x)!=ffa(tt[i].y))
{
ins(tt[i].x,tt[i].y);
ins(tt[i].y,tt[i].x);
fa[ffa(tt[i].x)]=tt[i].y;
tt[i].bj=;
}
}
dep[]=;cnt=;
for(int i=;i<=n;i++) if(ffa(i)==i)
{
dfs(i,);
dfs2(i,i);
}
build(,n); ans[]=;
for(int i=ll;i>=;i--)
{
if(tt[i].bj==) continue;
if(tt[i].bj==-)
{
fchange(tt[i].x,tt[i].y);
}
else
{
if(ffa(tt[i].x)!=ffa(tt[i].y)) ans[++ans[]]=-;
else ans[++ans[]]=fquery(tt[i].x,tt[i].y);
}
}
for(int i=ans[];i>=;i--)
{
if(ans[i]==) printf("Yes\n");
else printf("No\n");
}
} int main()
{
solve();
return ;
}
【是不是打的有点丑
2017-03-27 10:33:13