保证了无论怎么破坏航线，图都会是一个连通图
也就是说，起码肯定有一棵生成树
考虑在生成树上U，V之间加边，会对树上各个点的割边情况产生什么影响
对于任意点对(u,v)，如果它们之间的最短路径不经过从U到V的树上路径，那是没有影响的
否则：关键路径的数目会减少
减少了多少？U，V之间树上路径经过的所有边
启发了我们可以把维护割边转化成区间加，树上的区间加当然是用树链剖分处理了
查询询问时，答案就是u到v的路径上没有被覆盖的边
（为什么这样是对的？如果被覆盖了，显然可以从其他边走，就不是割边了）
但是删边不好处理，考虑到询问可以离线，把所有询问离线下来逆向处理，就只有加边而无删边操作了
有一些要注意的细节：
因为维护的其实是边权，所以要把点权下放到边权，修改的时候记得特判一下lca（细节见代码）
其次是，在不考虑会被删掉的边之外，剩下的图任然是一个连通图，不一定是树
那些既没在树上的，又没被删掉的边，要在处理询问前先加回去（不然有笨蛋会get 0 tips）
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn=2*int(1e5)+7;
ll cnt=0,ecnt=1;
ll n,m,R,old[maxn],id[maxn],wt[maxn],top[maxn],son[maxn],head[maxn],fa[maxn],siz[maxn],dep[maxn];
ll mod,a[maxn<<2],lazy[maxn<<2],w[maxn];
int ed[maxn],vis[maxn],ontree[maxn<<1];
struct lys{
int from,to,nex;
}e[maxn*2];
void addedge(int from,int to){
ecnt++;e[ecnt].from=from;e[ecnt].to=to;e[ecnt].nex=head[from];head[from]=ecnt;
}
void dfs1(int u,int f){
vis[u]=1;
siz[u]=1;
fa[u]=f;
dep[u]=dep[f]+1;
int maxson=-1;
for(int i=head[u];i;i=e[i].nex){
int to=e[i].to;
if(to==f||vis[to]) continue;
ed[to]=i;
ontree[i]=ontree[i^1]=1;
dfs1(to,u);
siz[u]+=siz[to];
if(siz[to]>maxson) son[u]=to,maxson=siz[to];
}
}
void dfs2(int u,int topf){
vis[u]=1;
cnt++;// dfs order
id[u]=cnt;
old[cnt]=u;
wt[cnt]=w[u];
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=head[u];i;i=e[i].nex){
int to=e[i].to;
if(to==son[u]||to==fa[u]||vis[to]) continue;
dfs2(to,to);
}
}
void pushup(int rt){
a[rt]=a[rt<<1]+a[rt<<1|1];
}
void build(int rt,int l,int r){
//
lazy[rt]=0;
if(l==r){
a[rt]= (ed[old[l]]!=-1);
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
pushup(rt);
}
void pushdown(int rt,int l,int r){
if(lazy[rt]){
lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
a[rt<<1]=a[rt<<1|1]=0;
lazy[rt]=0;
}
}
void add(int rt,int l,int r,int ql,int qr,ll k){
if(ql<=l&&r<=qr){
lazy[rt]+=k;
a[rt]=0;
return;
}
int mid=(l+r)>>1;
pushdown(rt,l,r);
if(ql<=mid) add(rt<<1,l,mid,ql,qr,k);
if(mid<qr) add(rt<<1|1,mid+1,r,ql,qr,k);
pushup(rt);
}
void addpath(int x,int y,ll k=1){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
add(1,1,n,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
//在同一条链上
// if dep[x]==dep[y] do nothing,else
if(dep[x]^dep[y]) add(1,1,n,id[x]+1,id[y],k);
}
ll query(int rt,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return a[rt];
}
pushdown(rt,l,r);
int mid=(l+r)>>1;ll ans=0;
if(mid>=ql) ans+=query(rt<<1,l,mid,ql,qr);
if(mid<qr) ans+=query(rt<<1|1,mid+1,r,ql,qr);
pushup(rt);
return ans;
}
ll qpath(int x,int y){
ll ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
// dep[x]<=dep[y]
ans+=query(1,1,n,id[x],id[y]);
// 减去lca
ans-=query(1,1,n,id[x],id[x]);
return ans;
}
map<ll,int>use;
int ID(int x,int y){
return x*10000+y;
}
int x[maxn],y[maxn],ans[maxn];
struct query{
int c,x,y;
}Q[maxn];
int main(){
//freopen("lys.in","r",stdin);
memset(ed,-1,sizeof(ed));
fastio;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x[i]>>y[i];
}
int qcnt=0;
while(1){
int c,xx,yy;cin>>c;
if(c==-1) break;
qcnt++;
cin>>xx>>yy;
Q[qcnt].c=c;Q[qcnt].x=xx,Q[qcnt].y=yy;
if(c==0) use[ID(xx,yy)]=use[ID(yy,xx)]=1;
}
for(int i=1;i<=m;i++){
if(use[ID(x[i],y[i])]||use[ID(y[i],x[i])]) continue;
//连通图，但不一定是树边
addedge(x[i],y[i]);
addedge(y[i],x[i]);
}
// 建立生成树
dfs1(1,0);
memset(vis,0,sizeof(vis));
dfs2(1,1);
build(1,1,n);
for(int i=2;i<=ecnt;i++){
int X=e[i].from,Y=e[i].to;
if(use[ID(X,Y)]||use[ID(Y,X)]) continue;//Be deleted
if(ontree[i]||ontree[i^1]) continue;
addpath(X,Y);
}
for(int i=qcnt;i>=1;i--){
if(Q[i].c==0){
addpath(Q[i].x,Q[i].y);
}
else {
ans[i]=qpath(Q[i].x,Q[i].y);
}
}
for(int i=1;i<=qcnt;i++){
if(Q[i].c==1) cout<<ans[i]<<endl;
}
}
标签：rt,LANE,AHOI2005,int,ll,离线,yy,dep,maxn From： https://www.cnblogs.com/liyishui2003/p/17282648.html