只有删边，想到时间倒流。
倒着加边，因为保证图连通，所以一开始一定至少是一棵树。我们先建一棵树出来，对于每一条非树边，两个端点在树上这段路径的边就不会变成关键边了，所以将它们对答案的贡献删去，那么直接树链剖分就好了。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #include<map> #define ll long long using namespace std; const int maxn=500010, inf=1e9; struct poi{int too, pre;}e[maxn]; struct tjm{int sum, tag;}tree[maxn<<2]; struct qwq{int ty, x, y;}q[maxn], a[maxn]; map<ll, bool>v; int n, m, ty, cnt, tot, tott, now; int last[maxn], size[maxn], fa[maxn], d[maxn], son[maxn], w[maxn], top[maxn], ans[maxn]; void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;} void dfs1(int x) { size[x]=1; for(int i=last[x], too;i;i=e[i].pre) { fa[too=e[i].too]=x; d[too]=d[x]+1; dfs1(too); size[x]+=size[too]; if(size[too]>size[son[x]]) son[x]=too; } } void dfs2(int x, int tp) { w[x]=++tott; top[x]=tp; if(son[x]) dfs2(son[x], tp); for(int i=last[x], too;i;i=e[i].pre) if((too=e[i].too)!=son[x]) dfs2(too, too); } inline void up(int x) {tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;} inline void down(int x) { if(!tree[x].tag) return; tree[x<<1].tag=1; tree[x<<1|1].tag=1; tree[x<<1].sum=tree[x<<1|1].sum=tree[x].tag=0; } void build(int x, int l, int r) { if(l==r) {tree[x].sum=1; return;} int mid=(l+r)>>1; build(x<<1, l, mid); build(x<<1|1, mid+1, r); up(x); } void update(int x, int l, int r, int cl, int cr) { if(cl<=l && r<=cr) {tree[x].tag=1; tree[x].sum=0; return;} down(x); int mid=(l+r)>>1; if(cl<=mid) update(x<<1, l, mid, cl, cr); if(cr>mid) update(x<<1|1, mid+1, r, cl, cr); up(x); } int query(int x, int l, int r, int cl, int cr) { if(cl<=l && r<=cr) return tree[x].sum; down(x); int mid=(l+r)>>1, ans=0; if(cl<=mid) ans=query(x<<1, l, mid, cl, cr); if(cr>mid) ans+=query(x<<1|1, mid+1, r, cl, cr); return ans; } inline int solve(int x, int y, int ty) { int f1=top[x], f2=top[y], ans=0; while(f1!=f2) { if(d[f1]<d[f2]) swap(x, y), swap(f1, f2); if(ty) update(1, 1, n, w[f1], w[x]); else ans+=query(1, 1, n, w[f1], w[x]); x=fa[f1]; f1=top[x]; } if(x==y) return ans; if(d[x]<d[y]) swap(x, y); if(ty) return update(1, 1, n, w[son[y]], w[x]), 0; return ans+query(1, 1, n, w[son[y]], w[x]); } int main() { read(n); read(m); for(int i=1;i<=m;i++) { read(a[i].x); read(a[i].y); if(a[i].x>a[i].y) swap(a[i].x, a[i].y); } read(ty); while(ty!=-1) { q[++cnt].ty=ty; if(ty) read(q[cnt].x), read(q[cnt].y); else { read(q[cnt].x); read(q[cnt].y); if(q[cnt].x>q[cnt].y) swap(q[cnt].x, q[cnt].y); v[1ll*q[cnt].x*66666+q[cnt].y]=1; } read(ty); } for(int i=1;i<=m && now<n-1;i++) if(!v[1ll*a[i].x*66666+a[i].y]) add(a[i].x, a[i].y), now++; dfs1(1); dfs2(1, 1); build(1, 1, n); for(int i=now+1;i<=m;i++) if(!v[1ll*a[i].x*66666+a[i].y]) solve(a[i].x, a[i].y, 1); for(int i=cnt;i;i--) if(q[i].ty) ans[++ans[0]]=solve(q[i].x, q[i].y, 0); else solve(q[i].x, q[i].y, 1); for(int i=ans[0];i;i--) printf("%d ", ans[i]); }