忽然意识到昨天交了十几发的CE是因为没选择语言qwq 本来准备按着题目分类刷一遍的，看来是刷不完了
思路还是挺简单的吧？ 把环拎出来单独处理(n条边的联通图存在且仅存在一个环)，那么若不考虑环 图中的连通图个数=总点数-"开"的边数 若这条环联通了，那么实际上有一条边并没有是减少联通块个数，但答案却已经减去了，所以ans++ 边的开合用树链剖分维护即可
#include<cstdio> #include<cctype> #include<algorithm> using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc();x=0; for(;!isdigit(c);c=nc()); for(;isdigit(c);c=nc())x=(x<<1)+(x<<3)+c-'0'; } const int N=300002; bool vis[N]; int n,m,head[N],nex[N<<1],to[N<<1],cnt,q[N],tot,c[N],c1,inc[N],bl[N]; struct data{int s,tag;}t[N<<3]; inline void addedge(int u,int v){ nex[++cnt]=head[u],head[u]=cnt,to[cnt]=v; } inline void getcyc(int x,int fa){ vis[x]=1,q[++tot]=x; for(int i=head[x];i;i=nex[i]) if(!vis[to[i]])getcyc(to[i],x); else if(to[i]!=fa){ if(c1)return; for(int y=0;y!=to[i];)y=q[tot--],c[++c1]=y,inc[y]=c1; }tot--; } int siz[N],dep[N],fa[N],son[N],top[N],pos[N],sz; inline void dfs1(int x){ siz[x]=1,dep[x]=dep[fa[x]]+1; for(int i=head[x];i;i=nex[i]){ if(to[i]==fa[x]||inc[to[i]])continue; fa[to[i]]=x,bl[to[i]]=bl[x],dfs1(to[i]),siz[x]+=siz[to[i]],son[x]=siz[to[i]]>siz[son[x]]?to[i]:son[x]; } } inline void dfs2(int x,int topf){ pos[x]=++sz,top[x]=topf; if(!son[x])return; dfs2(son[x],topf); for(int i=head[x];i;i=nex[i])if(to[i]!=fa[x]&&!inc[to[i]]&&to[i]!=son[x])dfs2(to[i],to[i]); } inline void pushdown(int x,int l,int r){ if(l==r||!t[x].tag)return; t[x].tag=0;int mid=l+r>>1; t[x<<1].tag^=1,t[x<<1|1].tag^=1; t[x<<1].s=mid-l+1-t[x<<1].s,t[x<<1|1].s=r-mid-t[x<<1|1].s; } inline void updata(int x,int l,int r,int L,int R){ if(L>R)return; if(l==L&&r==R){ t[x].tag^=1,t[x].s=r-l+1-t[x].s;return; } pushdown(x,l,r);int mid=l+r>>1; updata(x<<1,l,mid,L,min(R,mid)),updata(x<<1|1,mid+1,r,max(L,mid+1),R); t[x].s=t[x<<1].s+t[x<<1|1].s; } inline int query(int x,int l,int r,int L,int R){ if(L>R)return 0; if(l==L&&r==R)return t[x].s; pushdown(x,l,r);int mid=l+r>>1; return query(x<<1,l,mid,L,min(R,mid))+query(x<<1|1,mid+1,r,max(L,mid+1),R); } inline void upd(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); updata(1,1,n+c1,pos[top[x]],pos[x]),x=fa[top[x]]; } if(dep[x]<dep[y])swap(x,y); updata(1,1,n+c1,pos[y]+1,pos[x]); } int main(){ read(n),read(m);int x,y,px,py; for(int u,v,i=1;i<=n;i++)read(u),read(v),addedge(u,v),addedge(v,u); getcyc(1,0); for(int i=1;i<=c1;i++)bl[c[i]]=c[i],dfs1(c[i]),dfs2(c[i],c[i]); while(m--){ read(x),read(y); if(bl[x]==bl[y])upd(x,y); else{ upd(x,bl[x]),upd(y,bl[y]),x=bl[x],y=bl[y],px=inc[x],py=inc[y]; if(px<py){ if(py-px<c1-py+px||py-px==c1-py+px&&c[px+1]<c[px==1?c1:px-1])updata(1,1,n+c1,px+1+n,py+n); else updata(1,1,n+c1,1+n,px+n),updata(1,1,n+c1,py+1+n,c1+n); }else{ if(px-py<c1-px+py||px-py==c1-px+py&&c[px-1]<c[px