[[AHOI2005] 航线规划]([AHOI2005] 航线规划 - 洛谷)

首先是树的经典套路，依次删边\(\Rightarrow\)倒着加边

然后问题就转化为了求两点间非环边的数量，且会不断加边

一直缩点肯定就会爆的比我的爆零还难看

那我们假设一开始是一棵树，若加一条边，就会形成一个环

那我们就可以先给每条边赋一个值，表示它对答案的贡献，则一开始所有的树边都是1，加了一条边后，假设这条边连接的点为\(u,v\)，则\(u,v\)在树上经过的路径的边值都要变成0，也就是说，除了一开始的树边，我们可以不用再添加新的边，直接把树上对应的路径的边权值化为0即可

假设我们现在已经加了\(n\)条边了，若我们再加一条边且这个边连接的点经过的路径上的点存在有\(k\)对点是新加入的\(n\)条边所连接了的

我们还是只用改变树上的边权值且在计算边数时不用管除树边外的边，改变边值时不加上非树边也不影响改变权值的边

因为树边外的边一加入就一定时环的一部分，即权值一定为0，所以计算时不用管；且在改变时，由非树边连接的点也可以通过树边到达，所以改变时不走非树边也没关系

对于这种修改一段相连的树上的边的权值还有访问的题，上树剖

具体实现时，一开始先用不会删的边搞一个生成树就行了（可以在树剖中实现，特判一下即可）

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mid (l+r>>1)
#define lson rt<<1
#define rson rt<<1|1
#define ls l,mid,lson
#define rs mid+1,r,rson
using namespace std;
const int N=1e6+5;
int n,m;
struct node{
	int u,v;
	bool f;
}edge[N];
int tot1;
struct node1{
	int op,u,v;
}ope[N];
map<pii,bool> mp;
int head[N],cnt=1;
struct node2{
	int nxt,v,val;
}tree[N<<1];
void add(int x,int y){
	tree[++cnt].v=y,tree[cnt].nxt=head[x],head[x]=cnt;
}
int fa[N],depth[N],sz[N],son[N];
void dfs1(int x){
	sz[x]=1;
	for(int i=head[x],y;i;i=tree[i].nxt)
		if(!sz[y=tree[i].v]&&!mp[pii(x,y)])
			depth[y]=depth[x]+1,fa[y]=x,dfs1(y),sz[x]+=sz[y],(sz[son[x]]<sz[y])&&(son[x]=y);
}
int dfn[N],tot,top[N];
void dfs2(int x,int tp){
	dfn[x]=++tot,top[x]=tp;
	if(son[x]) dfs2(son[x],tp);
	for(int i=head[x],y;i;i=tree[i].nxt){
		if((y=tree[i].v)==fa[x]||y==son[x]||fa[y]!=x) continue;
		dfs2(y,y);
	}
}
struct node4{
	int sum;
	bool flag;
}tr[N<<1];
void up(int rt){
	tr[rt].sum=tr[lson].sum+tr[rson].sum;
}
void build(int l,int r,int rt){
	if(l==r){
		tr[rt].sum=1;
		return;
	}
	build(ls),build(rs),up(rt);
}
void down(int rt){
	tr[lson].flag=tr[rson].flag=1,tr[rt].flag=tr[lson].sum=tr[rson].sum=0;
}
void update(int l,int r,int rt,int a,int b){
	if(a<=l&&r<=b){
		tr[rt].flag=1,tr[rt].sum=0;
		return;
	}
	if(tr[rt].flag) down(rt);
	if(mid>=a) update(ls,a,b);
	if(mid<b) update(rs,a,b);
	up(rt);
}
void modify(int x,int y){
	if(x==y) return;
	while(top[x]!=top[y]){
		if(depth[top[x]]<depth[top[y]]) swap(x,y);
		update(1,n,1,dfn[top[x]],dfn[x]),x=fa[top[x]];
	}
	int t1=max(dfn[x],dfn[y]),t2=min(dfn[x],dfn[y]);
	if(t1==t2) return;
	update(1,n,1,t2+1,t1);
}
int get(int l,int r,int rt,int a,int b){
	if(a<=l&&r<=b) return tr[rt].sum;
	int ans=0;
	if(tr[rt].flag) down(rt);
	if(mid>=a) ans+=get(ls,a,b);
	if(mid<b) ans+=get(rs,a,b);
	up(rt);
	return ans;
}
int ask(int x,int y){
	if(x==y) return 0;
	int ans=0;
	while(top[x]!=top[y]){
		if(depth[top[x]]<depth[top[y]]) swap(x,y);
		ans+=get(1,n,1,dfn[top[x]],dfn[x]),x=fa[top[x]];
	}
	int t1=max(dfn[x],dfn[y]),t2=min(dfn[x],dfn[y]);
	if(t1==t2) return ans;
	return ans+get(1,n,1,t2+1,t1);
}
int ans[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d%d",&edge[i].u,&edge[i].v),add(edge[i].u,edge[i].v),add(edge[i].v,edge[i].u);
	while(scanf("%d",&ope[++tot1].op)&&ope[tot1].op!=-1){
		scanf("%d%d",&ope[tot1].u,&ope[tot1].v);
		if(!ope[tot1].op) mp[pii(ope[tot1].u,ope[tot1].v)]=mp[pii(ope[tot1].v,ope[tot1].u)]=true;
	} --tot1;
	depth[1]=1,dfs1(1),dfs2(1,1);
	build(1,n,1);
	for(int i=1;i<=m;++i) if(!mp[pii(edge[i].u,edge[i].v)]&&fa[edge[i].u]!=edge[i].v&&fa[edge[i].v]!=edge[i].u) modify(edge[i].u,edge[i].v);
	for(int i=tot1;i;--i){
		if(ope[i].op==0) modify(ope[i].u,ope[i].v);
		else ans[i]=ask(ope[i].u,ope[i].v);
	}
	for(int i=1;i<=tot1;++i) if(ope[i].op) printf("%d\n",ans[i]);
	return 0;
}