练一下树剖的板子，运用一下时间倒流和下放边权的思想。
题中所谓“关键航线”其实就是桥。
删边操作桥不好维护，但如果是加边，每加一条边，两点作为端点的这条路径就都不再是桥----->考虑时间倒流。
从后往前，每删除一条边，现在就是加边，该路径上所有边都不是桥（打上标记）。
可以先求出一棵最小生成树（代码中是在dfs中实现的）那些多的边就以加边的方式加入（说明到最后一个操作后，这条路径的边也不是桥）。
#include<bits/stdc++.h>
#define M 200003
#define N 60003
using namespace std;
int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
map<pair<int,int>,int>ma;
int fa[N],top[N],siz[N],head[N],dep[N],vis[N],son[N],pos[N];
int sum[N<<2],mark[N<<2],n;
struct EDGE{
int nextt,to,del,used;
}w[M*4];
struct Q{
int x,y,op,ans;
}q[M];
int tot=1;
void add(int a,int b)
{
tot++;
w[tot].nextt=head[a];
w[tot].to=b;
head[a]=tot;
}
void dfs1(int x)
{
vis[x]=1;//用vis，因为可能有环
siz[x]=1;
int maxson=-1;
for(int i=head[x];i;i=w[i].nextt)
{
int v=w[i].to;
if(vis[v]||w[i].del)continue;
fa[v]=x;dep[v]=dep[x]+1;
w[i].used=1;w[i^1].used=1;//在dfs中处理出最小生成树
dfs1(v);
siz[x]+=siz[v];
if(maxson<siz[v])son[x]=v,maxson=siz[v];
}
}
int cnt=0;
void dfs2(int x,int topf)
{
vis[x]=1;
pos[x]=++cnt;
top[x]=topf;
if(!son[x])return;
dfs2(son[x],topf);
for(int i=head[x];i;i=w[i].nextt)
{
int v=w[i].to;
if(vis[v]||v==son[x]||w[i].del)continue;
dfs2(v,v);
}
}
void build(int k,int l,int r)
{
if(l==r)
{
sum[k]=1;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
void pushdown(int k,int l,int r)
{
if(!mark[k])return;
mark[k<<1]=mark[k<<1|1]=1;
sum[k<<1]=sum[k<<1|1]=0;
mark[k]=0;
}
void modify(int k,int L,int R,int l,int r)
{
if(L>=l&&R<=r)
{
sum[k]=0;
mark[k]=1;
return;
}
int mid=(L+R)>>1;
pushdown(k,L,R);
if(l<=mid)modify(k<<1,L,mid,l,r);
if(r>mid)modify(k<<1|1,mid+1,R,l,r);
sum[k]=sum[k<<1|1]+sum[k<<1];
}
void range(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
modify(1,1,n,pos[top[x]],pos[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
modify(1,1,n,pos[x]+1,pos[y]);//下放边权，注意lca的位置
}
int query(int k,int L,int R,int l,int r)
{
int res=0;
if(L>=l&&R<=r)return sum[k];
int mid=(L+R)>>1;
pushdown(k,L,R);
if(l<=mid)res+=query(k<<1,L,mid,l,r);
if(r>mid)res+=query(k<<1|1,mid+1,R,l,r);
return res;
}
int querysum(int x,int y)
{
int res=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
res+=query(1,1,n,pos[top[x]],pos[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
res+=query(1,1,n,pos[x]+1,pos[y]);
return res;
}
int main()
{
n=read();int m=read();
for(int i=1;i<=m;++i)
{
int a=read(),b=read();
if(a>b)swap(a,b);
add(a,b);add(b,a);
ma[make_pair(a,b)]=i;
}
int c=read();
int ge=0;
while(c!=-1)
{
int a=read(),b=read();
if(a>b)swap(a,b);
q[++ge].op=c;
q[ge].x=a;q[ge].y=b;
if(c==0)
{
int id=ma[make_pair(a,b)];
w[id*2].del=1;w[id*2+1].del=1;
}
c=read();
}
dep[1]=1;
dfs1(1);
memset(vis,0,sizeof(vis));
dfs2(1,1);
build(1,1,n);
for(int i=2;i<=tot;i+=2)
{
if(w[i].del||w[i].used)continue;
range(w[i].to,w[i^1].to);
}
for(int i=ge;i>=1;--i)
{
if(q[i].op==0)range(q[i].x,q[i].y);
else q[i].ans=querysum(q[i].x,q[i].y);
}
for(int i=1;i<=ge;++i)
if(q[i].op==1)printf("%d\n",q[i].ans);
}
View Code