本文主要是介绍[AHOI2005]航线规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
航线规划
题解
好水一树剖
最先看到这道题时，有点像缩点，不过又不知道缩点咋搞，于是想到了树剖。
我们会发现这是一个连通图呀，可联通图又该咋搞呢？我们发现一句很重要的话：
航线破坏后不可恢复
要求的又是关键航线，于是我们便想到了树。假设我们一直把它删下去，那么我们一定会得到一棵有n-1条边的树。既然图不好处理，我们为什么不反向把它变成一棵树呢？
所以我们就把它离线下来，从最后的状态建成一棵树。删边的操作看成加边的操作。我们先把每条边的边权赋成1，如果加边，一定会形成一个环，在将环上的边的边权改为0，明显的树剖板子了。可最后得到的图不一定是一棵树，所以我们还要把最后的图抽成一棵树，用并查集维护两点之间是否已连接，依次加最后图上的边时判断是否已连接，若已连接还要对它进行修改。
之后从后往前离线处理它所有的操作，也就是树上的修改与查询。
这样，就可以轻松将它切掉了。
源码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define MAXN 50010
#define MAXM 100010
typedef long long LL;
typedef pair<LL,LL> pii;
#define int LL
#define gc() getchar()
const int INF=0x7f7f7f7f;
template<typename _T>
inline void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
int from[MAXM<<1],to[MAXM<<1];
int n,m,nxt[MAXM<<1];
int cnt,tot,head[MAXN],tt;
int dep[MAXN],wson[MAXN],siz[MAXN];
int father[MAXN],dfn[MAXN],ltp[MAXN],pre[MAXN];
int lzy[MAXN<<2],seg[MAXN<<2],val[MAXN];
void addEdge(int u,int v){from[++tot]=u;to[tot]=v;nxt[tot]=head[u];head[u]=tot;
}
void dfs1(int u){siz[u]=1;wson[u]=ltp[u]=0;for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==father[u])continue;dep[v]=dep[u]+1;father[v]=u;val[v]=1;dfs1(v);siz[u]+=siz[v];if(siz[wson[u]]<siz[v])wson[u]=v;}
}
void dfs2(int u,int tp){dfn[u]=++cnt;pre[cnt]=u;ltp[u]=tp;if(!wson[u]) return;dfs2(wson[u],tp);for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==father[u]||v==wson[u])continue;dfs2(v,v);}
}
void pushdown(int rt,int l,int r){if(lzy[rt]){seg[rt<<1]=seg[rt<<1|1]=0;lzy[rt<<1]=lzy[rt<<1|1]=1;lzy[rt]=0;}
}
void pushup(int rt){seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}
void build(int rt,int l,int r){lzy[rt]=0;if(l==r)return (void)(seg[rt]=val[l]);int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt);
}
void modify(int al,int ar,int rt,int l,int r){if(al<=l&&r<=ar)return (void)(seg[rt]=0,lzy[rt]=1);int mid=l+r>>1;pushdown(rt,l,r);if(al<=mid)modify(al,ar,rt<<1,l,mid);if(ar>mid)modify(al,ar,rt<<1|1,mid+1,r);pushup(rt);//printf("%d %d %d\n",l,r,segsum[rt]);
}
int query(int al,int ar,int rt,int l,int r){if(al<=l&&r<=ar)return seg[rt];int mid=l+r>>1,res=0;pushdown(rt,l,r);if(al<=mid)res=res+query(al,ar,rt<<1,l,mid);if(ar>mid)res=res+query(al,ar,rt<<1|1,mid+1,r);pushup(rt);return res;
}
int chainQuery(int u,int v){if(u==v)return 0;int res=0;for(int fu=ltp[u],fv=ltp[v];fu^fv;u=father[fu],fu=ltp[u]){if(dep[fu]<dep[fv])swap(u,v),swap(fu,fv);res=res+query(dfn[fu],dfn[u],1,1,n);} if(dep[u]>dep[v])swap(u,v);res=res+query(dfn[u]+1,dfn[v],1,1,n);return res;
}
void chainModify(int u,int v){if(u==v)return ;for(int fu=ltp[u],fv=ltp[v];fu^fv;u=father[fu],fu=ltp[u]){if(dep[fu]<dep[fv])swap(u,v),swap(fu,fv);modify(dfn[fu],dfn[u],1,1,n);} if(dep[u]>dep[v])swap(u,v);modify(dfn[u]+1,dfn[v],1,1,n);
}
int U[MAXM],V[MAXM],fa[MAXN],ans[MAXN],anspos;
int opt[MAXN],a[MAXN],b[MAXN];
map<int,int>mp[MAXN];
void makeSet(int x){for(int i=1;i<=x;i++)fa[i]=i;
}
int findSet(int x){if(x!=fa[x])fa[x]=findSet(fa[x]);return fa[x];
}
void unionSet(int x,int y){int u=findSet(x),v=findSet(y);if(u!=v)fa[u]=v;
}
vector<pii> vec;
signed main(){ read(n);read(m);for(int i=1;i<=m;i++){int u,v;read(u);read(v);mp[u][v]=mp[v][u]=1;U[i]=u;V[i]=v;}int toti=1;while(scanf("%d",&opt[toti])!=EOF){if(opt[toti]!=0&&opt[toti]!=1)break;read(a[toti]);read(b[toti]);if(!opt[toti])mp[a[toti]][b[toti]]=mp[b[toti]][a[toti]]=0;toti++;}makeSet(n);for(int i=1;i<=m;i++){int u=U[i],v=V[i];if(!mp[u][v])continue;if(findSet(u)!=findSet(v)){addEdge(u,v);addEdge(v,u);unionSet(u,v);continue;}vec.push_back(make_pair(u,v));}int siz=vec.size();dfs1(1);dfs2(1,1);build(1,1,n);for(int i=0;i<siz;i++){int u=vec[i].first,v=vec[i].second;chainModify(u,v);}for(int i=toti-1;i>0;i--){if(opt[i]==0)chainModify(a[i],b[i]);if(opt[i]==1)ans[++anspos]=chainQuery(a[i],b[i]);}for(int i=anspos;i>0;i--)printf("%d\n",ans[i]);return 0;
}谢谢！！！
这篇关于[AHOI2005]航线规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
