显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<map>
#include<set>
#include<cmath>
#include<deque>
using namespace std;
const int SIZEN=30010,SIZEC=20,SIZEM=40010;
int N,M;
class miku//兹次改段求点的树状数组
{
public:
int n;
int Bit[SIZEN];//维护差分系列的数组
void clear(int x){n=x,memset(Bit,0,sizeof(Bit));}
int lowbit(int x){return x&(-x);}
void change_t(int x,int t)
{
while(x>0)
{
Bit[x]+=t;
x-=lowbit(x);
}
}
void change(int l,int r,int t)
{
change_t(r,t);
change_t(l-1,-t);
}
int nov(int x)
{
int ans=0;
while(x<=n) {ans+=Bit[x],x+=lowbit(x);}
return ans;
}
void print()
{
cout<<n<<endl;
for(int i=1;i<=N;i++)
cout<<Bit[i]<<" ";
}
};
miku Tr;
class poi//询问
{
public:
int c;
int fr,to;
};
deque<poi> D;
deque<pair<int,int> > s[SIZEN];
bool visit[SIZEN]={0};
int tot=0,tot1=0,tot2=0;//边，删边，查询
int pre[SIZEN]={0},ufs[SIZEN]={0};
int dfslist[SIZEN*2]={0},dfslen=0,first[SIZEN]={0};
int ST[2*SIZEN][SIZEC]={0};
set<pair<int,int> > E;
int f[SIZEN]={0},low[SIZEN]={0},tim=0,po=0,son[SIZEN]={0};
deque<int> ans;
void Swap(int &a,int &b){ int t=a;a=b;b=t;}
int get(int x)
{
//cout<<x<<" "<<pre[x]<<endl;
return Tr.nov(pre[x]);
}
int grand(int x)
{
if(ufs[x]==x) return x;
return ufs[x]=grand(ufs[x]);
}
int STLCA(int x,int y)
{
int l=first[x],r=first[y];
if(l>r) Swap(l,r);
int m=int(log2(r-l+1.0));
int a=ST[l][m],b=ST[r-(1<<m)+1][m];
if(get(a)<get(b)) return a;
else return b;
}
int getdeep(int x,int y)
{
int temx=grand(x),temy=grand(y);
if(temx==temy) return 0;
int A=STLCA(temx,temy);
return get(temx)+get(temy)-2*get(A);
}
void adde(int x,int y)
{
int temx=grand(x),temy=grand(y);
if(temx==temy) return;
int A=grand(STLCA(temx,temy)),ac=get(A);
deque<int> c;
for(int i=temx;i!=A;i=grand(f[i])) c.push_back(i);
for(int i=c.size()-1;i>=0;i--) Tr.change(pre[c[i]],pre[c[i]]+son[c[i]]-1,-1),ufs[c[i]]=A;
c.clear();
for(int i=temy;i!=A;i=grand(f[i])) c.push_back(i);
for(int i=c.size()-1;i>=0;i--) Tr.change(pre[c[i]],pre[c[i]]+son[c[i]]-1,-1),ufs[c[i]]=A;
}
void work()
{
for(int i=D.size()-1;i>=0;i--)
{
if(D[i].c==1) ans.push_front(getdeep(D[i].fr,D[i].to));
else adde(D[i].fr,D[i].to);
}
for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]);
}
void make_ST()
{
int t=int(log2(dfslen+0.0));
for(int i=1;i<=dfslen;i++) ST[i][0]=dfslist[i];
for(int i=1;i<=t;i++)
for(int j=1;j<=dfslen;j++)
{
if(j+(1<<i)-1>dfslen) continue;
if(get(ST[j][i-1])<get(ST[j+(1<<(i-1))][i-1])) ST[j][i]=ST[j][i-1];
else ST[j][i]=ST[j+(1<<(i-1))][i-1];
}
}
void make_DCC(int x,int sst,int dep)//求强连通分量
{
if(visit[x]) return;
visit[x]=1;
dfslist[++dfslen]=x;first[x]=dfslen;ufs[x]=sst;
Tr.change(pre[x],pre[x],dep);
for(int i=0;i<s[x].size();i++)
{
int v=s[x][i].first;
if(visit[v]) continue;
if(s[x][i].second) make_DCC(v,v,dep+1);
else make_DCC(v,sst,dep);
dfslist[++dfslen]=x;
}
}
int tarjin(int x)
{
int lowu=pre[x]=++tim;
for(int i=0;i<s[x].size();i++)
{
int v=s[x][i].first;
if(v==f[x]) continue;
if(!pre[v])
{
f[v]=x;int lowv=tarjin(v);
if(lowv>pre[x]) s[x][i].second=1;
lowu=min(lowu,lowv);
}
else
{
lowu=min(pre[v],lowu);
}
}
son[x]=tim-pre[x]+1;low[x]=lowu;
return lowu;
}
void read()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++)
{
int u,v;
scanf("%d%d",&u,&v);
if(u>v) Swap(u,v);
E.insert(make_pair(u,v));
}
poi T;
pair<int,int> pr;
while(true)
{
scanf("%d",&T.c);
if(T.c==-1) break;
scanf("%d%d",&T.fr,&T.to);
if(T.fr>T.to) Swap(T.fr,T.to);
D.push_back(T);
if(T.c==0)
{
pr.first=T.fr,pr.second=T.to;
E.erase(E.find(pr));
}
}
set<pair<int,int> >::iterator it;
for(it=E.begin();it!=E.end();it++)
{
int u=it->first,v=it->second;
s[u].push_back(make_pair(v,0));
s[v].push_back(make_pair(u,0));
}
Tr.clear(N);
}
int main()
{
freopen("lane.in","r",stdin);
freopen("lane.out","w",stdout);
read();
tarjin(1);
make_DCC(1,1,0);
make_ST();
work();
//cout<<"FUCK YOU"<<endl;
return 0;
}
mikumikumi