显示代码纯文本
#include <cstdio>
#include <cstring>
#include <set>
#define maxn 30005
#define maxx 280005
#define maxa 120005
#define mem(a,b) memset(a,b,sizeof(a))
inline void read(int& x)
{ char c=getchar();x=0;int y=1;
while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
x*=y;
}
int n,m,num,rnum,bnum,hea[maxn],bccsum,cnt,bsum,nnum,nhea[maxn];
int f[maxn],dp[maxn],top[maxn],tn[maxn],ssum[maxn],son[maxn];
int st[maxn],topp,low[maxn],dfn[maxn],dfn_clock,bel[maxn],fans[40005],fsum;
bool inst[maxn],cov[maxa],qu[40005];
struct tree{int lc,rc;}tr[maxa];
int sum[maxa];
struct road{int be,en,nex;}ro[maxx],nnro[maxx];
inline void build(int x,int y,int z)
{ tr[z].lc=x;tr[z].rc=y;
if(x==y){sum[z]=1;return;}
int mid=x+y>>1;
build(x,mid,z<<1);build(mid+1,y,z<<1|1);
sum[z]=sum[z<<1]+sum[z<<1|1];
}
inline void update(int x,int y,int z)
{ if(tr[z].lc>=x&&tr[z].rc<=y){sum[z]=0,cov[z]=1;return;}
if(cov[z])
{ int lch=z<<1,rch=lch|1;
cov[lch]=cov[rch]=1;sum[lch]=sum[rch]=0;
}
int mid=tr[z].lc+tr[z].rc>>1;
if(x<=mid) update(x,y,z<<1);
if(mid<y) update(x,y,z<<1|1);
sum[z]=sum[z<<1]+sum[z<<1|1];
}
inline int query(int x,int y,int z)
{ if(tr[z].lc>=x&&tr[z].rc<=y) return sum[z];
if(cov[z])
{ int lch=z<<1,rch=lch|1;
cov[lch]=cov[rch]=1;sum[lch]=sum[rch]=0;
}
int mid=tr[z].lc+tr[z].rc>>1,tmp=0;
if(x<=mid) tmp+=query(x,y,z<<1);
if(mid<y) tmp+=query(x,y,z<<1|1);
return tmp;
}
struct node
{ int be,en;
friend bool operator<(const node& a,const node& b){return a.be==b.be?a.en<b.en:a.be<b.be;}
}nro[40005],tro[200005];
std::set<node>S;
inline void tarjan(int x,int y=0)
{ low[x]=dfn[x]=++dfn_clock;st[++topp]=x;inst[x]=1;
for(int i=nhea[x];i;i=nnro[i].nex)
{ int v=nnro[i].en;
if(v==y) continue;
if(!dfn[v])
{ tarjan(v,x);
if(low[x]>low[v]) low[x]=low[v];
}
else if(inst[v]&&low[x]>dfn[v]) low[x]=dfn[v];
}
if(low[x]==dfn[x])
{ int tmp;++bccsum;
while(1)
{ tmp=st[topp--];inst[tmp]=0;
bel[tmp]=bccsum;
if(tmp==x) break;
}
}
}
inline void dfs(int x,int y=0)
{ ssum[x]=1;f[x]=y;dp[x]=dp[y]+1;
for(int i=hea[x];i;i=ro[i].nex)
{ int v=ro[i].en;
if(v==y) continue;
dfs(v,x);
ssum[x]+=ssum[v];
if(!son[x]||ssum[son[x]]<ssum[v]) son[x]=v;
}
}
inline void redfs(int x,int y)
{ top[x]=y;tn[x]=++cnt;
if(!son[x]) return;
redfs(son[x],y);
for(int i=hea[x];i;i=ro[i].nex)
{ int v=ro[i].en;
if(v!=f[x]&&v!=son[x]) redfs(v,v);
}
}
inline int getnum(int x,int y)
{ int t1=top[x],t2=top[y],tmp=0;
while(t1^t2)
{ if(dp[t1]<dp[t2]) std::swap(t1,t2),std::swap(x,y);
tmp+=query(tn[t1],tn[x],1);
x=f[t1];t1=top[x];
}
if(dp[x]>dp[y]) std::swap(x,y);
if(tn[x]!=tn[y]) tmp+=query(tn[x]+1,tn[y],1);
return tmp;
}
inline void paint(int x,int y)
{ int t1=top[x],t2=top[y];
while(t1^t2)
{ if(dp[t1]<dp[t2]) std::swap(t1,t2),std::swap(x,y);
update(tn[t1],tn[x],1);
x=f[t1];t1=top[x];
}
if(dp[x]>dp[y]) std::swap(x,y);
if(tn[x]!=tn[y]) update(tn[x]+1,tn[y],1);
}
int solve()
{ freopen("lane.in","r",stdin);
freopen("lane.out","w",stdout);
read(n);read(m);int x,y,z;
register int i;
for(i=1;i<=m;++i){read(x);read(y);tro[++bsum].be=x;tro[bsum].en=y;tro[++bsum].be=y;tro[bsum].en=x;}
read(x);
while(x!=-1)
{ read(y);read(z);
if(!x) nro[++rnum].be=y,nro[rnum].en=z,S.insert((node){z,y}),S.insert((node){y,z});
else nro[++rnum].be=y,nro[rnum].en=z,qu[rnum]=1;
read(x);
}
for(i=1;i<=bsum;++i)
if(!S.count(tro[i]))
{ nnro[++nnum].be=tro[i].be;nnro[nnum].en=tro[i].en;
nnro[nnum].nex=nhea[tro[i].be];nhea[tro[i].be]=nnum;
}
for(i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
for(i=0;i<nnum;++i)
if(bel[nnro[i].be]!=bel[nnro[i].en])
ro[++num].en=bel[nnro[i].en],ro[num].nex=hea[bel[nnro[i].be]],hea[bel[nnro[i].be]]=num;
dfs(1);redfs(1,1);build(1,bccsum,1);
for(i=rnum;i>=1;--i)
if(qu[i]) fans[++fsum]=getnum(bel[nro[i].be],bel[nro[i].en]);
else
{ if(bel[nro[i].be]==bel[nro[i].en]) continue;
paint(bel[nro[i].be],bel[nro[i].en]);
}
for(i=fsum;i>=1;--i) printf("%d\n",fans[i]);
return 0;
}
int Anonymity=solve();
int main(){;}
Anonymity