题解 P2542 【[AHOI2005]航线规划】

题解在博客[食用](https://www.cnblogs.com/YoungNeal/p/9147556.html)效果更佳哦~ 楼下dalao的lct我并不会 只会蒻蒻的树剖qwq ## Hint 我们保证无论航线如何被破坏，任意时刻任意两个星球都能够相互到达。在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。 ## Solution 首先这题离线逆序处理不必多说了，这类删除点/边题固定套路 刚看到这题的想法是 $Tarjan$ 缩点然后怎么拓扑乱搞求一下距离 然而这是一个无向图并不存在拓扑序 然而我并不会求距离 我们注意到 $Hint$ 里面保证了这么一句话```在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。``` 题目保证不存在重边，而且互相连通，又是无向图...想到了什么？缩完点后的图是一棵树啊！ 也就是说，我们需要动态的维护树上点之间的距离 树上把点连起来的是什么？边啊！ 那么我们需要维护树上两点之间的边权不就行了！ 想到了什么？树链剖分！ 对，我们可以树剖维护树上的边权，这样就可以轻而易举的求出树上两点之间的距离了。 那...怎么动态缩点呢？ 做这题时，我为这事纠结了半天... 然后才发现，既然能维护树上两点间距离，那还缩点干啥呢？ 直接将一个环内的点之间的边权赋为0不就行了！ 算法流程如下： 0. 读入询问，逆序处理 1. 先随便在原图中求出一棵生成树，我直接用 $dfs$ 序实现的 2. 然后用那些没被删除的非树边先更新一遍当前的边权 3. 树剖裸题。 因为是边权下放到点权，注意修改的时候不要改它们的 $lca$ ！ ## Code ```cpp #include<map> #include<cstdio> #include<cctype> #define N 30005 #define Q 40005 #define M 100005 #define max(A,B) ((A)>(B)?(A):(B)) #define min(A,B) ((A)<(B)?(A):(B)) #define swap(A,B) ((A)^=(B)^=(A)^=(B)) int n,m,d[N],ans[Q]; std::map<int,int> mp; int cnt,tot,son[N],pos; int val[N],head[N],fa[N]; int dfn[N],top[N],ques[Q][5]; int sze[N],sum[N<<2],lazy[N<<2]; struct Edge{ int to,nxt,ok; }edge[M<<1]; void add(int x,int y){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt; mp[x*(n+1)+y]=cnt;; } int getint(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*f; } void first_dfs(int now){ sze[now]=1; for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(sze[to] or edge[i].ok) continue; d[to]=d[now]+1; fa[to]=now; first_dfs(to); sze[now]+=sze[to]; if(sze[to]>sze[son[now]]) son[now]=to; } } void second_dfs(int now,int low){ dfn[now]=++tot; top[now]=low; if(son[now]) second_dfs(son[now],low); for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(fa[to]!=now or to==son[now] or edge[i].ok) continue; second_dfs(to,to); } } void pushup(int cur){ sum[cur]=sum[cur<<1]+sum[cur<<1|1]; } void build(int cur,int l,int r){ if(l==r){ sum[cur]=1; return; } int mid=l+r>>1; build(cur<<1,l,mid); build(cur<<1|1,mid+1,r); pushup(cur); } void pushdown(int cur){ if(!lazy[cur]) return; sum[cur<<1]=sum[cur<<1|1]=0; lazy[cur<<1]=lazy[cur<<1|1]=1; lazy[cur]=0; } void modify(int cur,int l,int r,int ql,int qr){ if(ql<=l and r<=qr){ sum[cur]=0; lazy[cur]=1; return; } pushdown(cur); int mid=l+r>>1; if(ql<=mid) modify(cur<<1,l,mid,ql,qr); if(mid<qr) modify(cur<<1|1,mid+1,r,ql,qr); pushup(cur); } void change(int x,int y){ while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]]) swap(x,y); modify(1,1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } if(d[x]<d[y]) swap(x,y); if(d[x]!=d[y]) modify(1,1,n,dfn[y]+1,dfn[x]); } void third_dfs(int now){ for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(edge[i].ok) continue; if(fa[to]==now) third_dfs(to); if(fa[now]!=to and d[to]<d[now]) change(to,now); } } int query(int cur,int l,int r,int ql,int qr){ if(ql<=l and r<=qr) return sum[cur]; pushdown(cur); int mid=l+r>>1,now=0; if(ql<=mid) now+=query(cur<<1,l,mid,ql,qr); if(mid<qr) now+=query(cur<<1|1,mid+1,r,ql,qr); return now; } int ask(int x,int y){ int now=0; while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]]) swap(x,y); now+=query(1,1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } if(d[x]<d[y]) swap(x,y); now+=query(1,1,n,dfn[y],dfn[x]); now-=query(1,1,n,dfn[y],dfn[y]); return now; } signed main(){ n=getint(),m=getint(); for(int i=1;i<=m;i++){ int x=getint(),y=getint(); add(x,y); add(y,x); } while(1){ int a=getint(); if(a==-1) break; int b=getint(),c=getint(); ques[++pos][1]=a; ques[pos][2]=b; ques[pos][3]=c; if(a==0) edge[mp[b*(n+1)+c]].ok=edge[mp[c*(n+1)+b]].ok=1; } d[1]=1; first_dfs(1); second_dfs(1,1); build(1,1,n); third_dfs(1); for(int i=pos;i;i--){ if(ques[i][1]) ans[i]=ask(ques[i][2],ques[i][3]); else change(ques[i][2],ques[i][3]); } for(int i=1;i<=pos;i++){ if(ques[i][1]!=1) continue; printf("%d\n",ans[i]); } return 0; } ```