dalao求助!
#include<iostream>
#include<cstdio>
#include<stack>
#include<set>
#define lson l,mid,num<<1
#define rson mid+1,r,num<<1|1
using namespace std;
const int maxn=1e4+5,maxq=4e4+5,maxm=1e5+5;
int n,m,k,op[maxq],a[maxq],b[maxq],ans[maxq],head[2][maxn];
int idx,npo,dfn[maxn],low[maxn],bel[maxn];
int cnt,tid[maxn],top[maxn],dep[maxn],son[maxn],rk[maxn],fa[maxn],sz[maxn],sum[maxn<<2],lzy[maxn<<2];
bool ins[maxn],vis[maxn];
set<pair<int,int> >edge;
stack<int>sta;
struct road
{
int en,nxt;
} ed[2][maxm<<1];
void buildedge(int p,int a,int b)
{
k++;
ed[p][k].nxt=head[p][a];
head[p][a]=k;
ed[p][k].en=b;
}
void tarjan(int x,int f)
{
sta.push(x);
ins[x]=true;
dfn[x]=low[x]=++idx;
for(int i=head[0][x];i!=-1;i=ed[0][i].nxt)
if(ed[0][i].en!=f)
{
if(!vis[ed[0][i].en]&&!ins[ed[0][i].en])
{
tarjan(ed[0][i].en,x);
low[x]=min(low[x],low[ed[0][i].en]);
}
if(ins[ed[0][i].en])
low[x]=min(low[x],ed[0][i].en);
}
if(dfn[x]==low[x])
{
int kpo;
npo++;
do
{
kpo=sta.top();
bel[kpo]=npo;
ins[kpo]=false;
sta.pop();
} while(kpo!=x);
}
vis[x]=true;
}
void dfs1(int x,int f)
{
dep[x]=dep[f]+1;
sz[x]=1;
fa[x]=f;
son[x]=-1;
for(int i=head[1][x]; i!=-1; i=ed[1][i].nxt)
if(ed[1][i].en!=f)
{
dfs1(ed[1][i].en,x);
sz[x]+=sz[ed[1][i].en];
if(son[x]==-1||sz[son[x]]<sz[ed[1][i].en])
son[x]=ed[1][i].en;
}
}
void dfs2(int x,int f)
{
tid[x]=++cnt;
rk[tid[x]]=x;
top[x]=f;
if(son[x]!=-1)
dfs2(son[x],f);
for(int i=head[1][x]; i!=-1; i=ed[1][i].nxt)
if(ed[1][i].en!=fa[x]&&ed[1][i].en!=son[x])
dfs2(ed[1][i].en,ed[1][i].en);
}
void pushdown(int num)
{
if(!lzy[num])
return;
sum[num<<1]=sum[num<<1|1]=0;
lzy[num<<1]=lzy[num<<1|1]=1;
lzy[num]=0;
}
void build(int l,int r,int num)
{
if(l==r)
{
sum[num]=1;
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
sum[num]=sum[num<<1]+sum[num<<1|1];
}
void update(int l,int r,int num,int be,int en)
{
if(l>=be&&r<=en)
{
sum[num]=0;
lzy[num]=1;
return;
}
pushdown(num);
int mid=(l+r)>>1;
if(be<=mid)
update(lson,be,en);
if(en>mid)
update(rson,be,en);
sum[num]=sum[num<<1]+sum[num<<1|1];
}
int query(int l,int r,int num,int be,int en)
{
if(l>=be&&r<=en)
return sum[num];
pushdown(num);
int mid=(l+r)>>1,rt=0;
if(be<=mid)
rt+=query(lson,be,en);
if(en>mid)
rt+=query(rson,be,en);
return rt;
}
void add(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]])
swap(x,y);
update(1,n,1,tid[top[y]],tid[y]);
y=fa[top[y]];
}
if(dep[x]>dep[y])
swap(x,y);
if(x!=y)
update(1,n,1,tid[son[x]],tid[y]);
}
int find(int x,int y)
{
int rt=0;
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]])
swap(x,y);
rt+=query(1,n,1,tid[top[y]],tid[y]);
y=fa[top[y]];
}
if(dep[x]>dep[y])
swap(x,y);
if(x!=y)
rt+=query(1,n,1,tid[son[x]],tid[y]);
return rt;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
head[0][i]=head[1][i]=-1;
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
edge.insert(make_pair(a,b));
edge.insert(make_pair(b,a));
}
int q=1;
scanf("%d",&op[q]);
while(op[q]!=-1)
{
scanf("%d%d",&a[q],&b[q]);
if(op[q]==0)
{
edge.erase(make_pair(a[q],b[q]));
edge.erase(make_pair(b[q],a[q]));
}
scanf("%d",&op[++q]);
}
q--;
int nedge=edge.size();
for(int i=1;i<=nedge;i++)
{
int x=(*edge.begin()).first,y=(*edge.begin()).second;
buildedge(0,(*edge.begin()).first,(*edge.begin()).second);
edge.erase(*edge.begin());
}
tarjan(1,1);
for(int i=1;i<=n;i++)
for(int j=head[0][i]; j!=-1; j=ed[0][j].nxt)
if(bel[i]!=bel[ed[0][j].en])
buildedge(1,bel[i],bel[ed[0][j].en]);
dfs1(1,1);
dfs2(1,1);
build(1,n,1);
for(int i=q;i>=1;i--)
{
if(op[i]==1)
ans[i]=find(bel[a[i]],bel[b[i]]);
if(op[i]==0)
add(bel[a[i]],bel[b[i]]);
}
for(int i=1;i<=q;i++)
if(op[i]==1)
printf("%d\n",ans[i]);
return 0;
}