显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
map<pair<int,int>,bool> S;
int n,m,a1,a2,cnt=0,tot=0;
int ff[30001],ans[200001];
struct PE
{
int u,v;
};
PE A[200001];
struct PES
{
int id,u,v;
};
PES q[200001];
vector<int> b[30001];
int id[30001],rk[30001],dep[30001],size[30001],top[30001],fa[30001],son[30001];
int val[120001],lazy[120001];
int Find(int x)
{
if(x==ff[x])
return x;
return ff[x]=Find(ff[x]);
}
void DFS1(int x,int f)
{
fa[x]=f;
size[x]=1;
dep[x]=dep[fa[x]]+1;
for(int i=0;i<b[x].size();i++)
{
int to=b[x][i];
if(to==fa[x])
continue;
DFS1(to,x);
size[x]+=size[to];
if(size[son[x]]<size[to])
son[x]=to;
}
}
void DFS2(int x,int tp)
{
id[x]=++cnt;
rk[cnt]=x;
top[x]=tp;
if(son[x])
DFS2(son[x],tp);
for(int i=0;i<b[x].size();i++)
{
int to=b[x][i];
if(to==son[x]||to==fa[x])
continue;
DFS2(to,to);
}
}
int ls(int x)
{
return x<<1;
}
int rs(int x)
{
return x<<1|1;
}
void pushup(int x)
{
val[x]=val[ls(x)]+val[rs(x)];
}
void pushdown(int x)
{
if(lazy[x])
{
val[ls(x)]=0;
val[rs(x)]=0;
lazy[ls(x)]=lazy[rs(x)]=1;
lazy[x]=0;
}
}
void build(int x,int l,int r)
{
if(l==r)
{
if(rk[l]!=1)
val[x]=1;
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x);
}
void Change(int x,int l,int r,int nl,int nr)
{
if(nl<=l&&nr>=r)
{
val[x]=0;
lazy[x]=1;
return;
}
pushdown(x);
int mid=(l+r)>>1;
if(nl<=mid)
Change(ls(x),l,mid,nl,nr);
if(nr>mid)
Change(rs(x),mid+1,r,nl,nr);
pushup(x);
}
int Query(int x,int l,int r,int nl,int nr)
{
if(nl<=l&&nr>=r)
{
return val[x];
}
pushdown(x);
int mid=(l+r)>>1,res=0;
if(nl<=mid)
res+=Query(ls(x),l,mid,nl,nr);
if(nr>mid)
res+=Query(rs(x),mid+1,r,nl,nr);
return res;
}
void Linkchange(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
Change(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]<dep[y])
swap(x,y);
if(id[x]!=id[y])
Change(1,1,n,id[y]+1,id[x]);
}
int Linkquery(int x,int y)
{
int res=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
//if(id[top[x]]==id[x])
res+=Query(1,1,n,id[top[x]],id[x]);
//else
// res+=Query(1,1,n,id[top[x]]+1,id[x]);
x=fa[top[x]];
}
if(dep[x]<dep[y])
swap(x,y);
if(id[y]!=id[x])
res+=Query(1,1,n,id[y]+1,id[x]);
return res;
}
int main()
{
freopen("lane.in","r",stdin);
freopen("lane.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a1,&a2);
A[i].u=a1;
A[i].v=a2;
}
while(1)
{
scanf("%d",&a1);
if(a1==-1)
break;
if(a1==0)
{
scanf("%d%d",&a1,&a2);
S[make_pair(a1,a2)]=1;
q[++tot].u=a1;
q[tot].v=a2;
q[tot].id=0;
}
else
{
scanf("%d%d",&a1,&a2);
q[++tot].u=a1;
q[tot].v=a2;
q[tot].id=1;
}
}
for(int i=1;i<=n;i++)
{
ff[i]=i;
}
for(int i=1;i<=m;i++)
{
int u=A[i].u;
int v=A[i].v;
int fu=Find(u);
int fv=Find(v);
if(S[make_pair(u,v)]||S[make_pair(v,u)]||(fu==fv))
{
continue;
}
ff[fv]=fu;
b[u].push_back(v);
b[v].push_back(u);
S[make_pair(u,v)]=1;
}
DFS1(1,0);
DFS2(1,1);
build(1,1,n);
//cout<<"S";
//cout<<Query(1,1,n,1,1);
//cout<<'*'<<Query(1,1,n,2,2)<<"S";
for(int i=1;i<=m;i++)
{
int u=A[i].u;
int v=A[i].v;
if(!(S[make_pair(u,v)]||S[make_pair(v,u)]))
{
Linkchange(u,v);
}
}
for(int i=tot;i>=1;i--)
{
if(q[i].id==0)
{
Linkchange(q[i].u,q[i].v);
}
else
{
ans[i]=Linkquery(q[i].u,q[i].v);
}
}
for(int i=1;i<=tot;i++)
{
if(q[i].id==1)
printf("%d\n",ans[i]);
}
return 0;
}
瑆の時間~無盡輪迴·林蔭