P2542 [AHOI2005] 航线规划 题解
P2542 [AHOI2005] 航线规划 题解
前言
本题我使用到的算法：Tarjan、树链剖分、线段树。
题意
给出一个无向图，要求支持两种操作：
-
求出给出的两点的路径中割边的数量。
-
删除两点之间的一条边。
思路
选择离线操作。在线操作比较麻烦，无法达到正确的时间复杂度。
首先将所有要删除的边删除，得到一个新的无向图。
接着将新的无向图使用 Tarjan 进行缩点，那么缩点之后就成了一颗树。
不难发现，两点路径中割边的数量即为在树上简单路径的长度。
我们可以使用线段树以及树剖，维护两点之间的权值和。
因为要求的是两点简单路径上的边数，所以初始时将除了根节点之外的每一个点赋值为
接着考虑删除的操作，因为我们一开始就将边给删去，所以正着做比较麻烦，所以不妨试试反着做。即从后往前循环，遇到一个删除操作，则将两点简单路径上的点的权值更改为
注意的是，因为我们是将点代表边，所以在操作时需要忽略根节点。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,cnt,l,num,p;
int dfn[N],low[N],now[N],siz[N],son[N],f[N],de[N],tp[N],id[N],ans[N];
stack<int>s;
vector<int>v[N],g[N];
struct ccf
{
int op,x,y;
}a[N];
struct tree
{
int l,r,la,sum;
}t[N<<2];
map<pair<int,int>,int>mp;
bool era(int x,int y)
{
if(x>y)swap(x,y);
return mp[make_pair(x,y)];//此边已删除
}
void tarjan(int x,int fa)
{
dfn[x]=low[x]=++cnt;
s.push(x);
for(int i=0;i<v[x].size();i++)
{
int to=v[x][i];
if(to==fa||era(x,to))continue;
if(!dfn[to])tarjan(to,x);
low[x]=min(low[x],low[to]);
}
if(low[x]==dfn[x])
{
int t=-1;
num++;
while(t!=x)
{
t=s.top();
s.pop();
now[t]=num;
}
}
}//缩点
void dfs1(int x,int fa)
{
f[x]=fa;
siz[x]=1;
de[x]=de[fa]+1;
int ma=0;
for(int i=0;i<g[x].size();i++)
{
int to=g[x][i];
if(to==fa)continue;
dfs1(to,x);
siz[x]+=siz[to];
if(siz[to]>ma)
ma=siz[to],son[x]=to;
}
}
void dfs2(int x,int top)
{
tp[x]=top;
id[x]=++p;
if(!son[x])return ;
dfs2(son[x],top);
for(int i=0;i<g[x].size();i++)
{
int to=g[x][i];
if(to==f[x]||to==son[x])continue;
dfs2(to,to);
}
}//树剖
void push_down(int k)
{
if(!t[k].la)return ;
int l=k*2,r=k*2+1;
t[l].la=1,t[r].la=1;
t[l].sum=0;
t[r].sum=0;
t[k].la=0;
}
void build(int k,int l,int r)
{
if(r<l)return ;
t[k].l=l,t[k].r=r;
if(l==r)
{
if(l!=1)t[k].sum=1;
return ;
}
int mid=(l+r)/2;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
t[k].sum=t[k*2].sum+t[k*2+1].sum;
}
void change(int k,int l,int r,int x,int y,int z)
{
if(l>y||r<x)return ;
if(x<=l&&r<=y)
{
t[k].sum=z;
t[k].la=1;
return ;
}
push_down(k);
int mid=(l+r)/2;
change(k*2,l,mid,x,y,z);
change(k*2+1,mid+1,r,x,y,z);
t[k].sum=t[k*2].sum+t[k*2+1].sum;
}
int ask(int k,int l,int r,int x,int y)
{
if(l>y||r<x)return 0;
if(x<=l&&r<=y)return t[k].sum;
push_down(k);
int mid=(l+r)/2;
return ask(k*2,l,mid,x,y)+ask(k*2+1,mid+1,r,x,y);
}//线段树操作，区间修改，区间查询
void add(int x,int y,int z)
{
while(tp[x]!=tp[y])
{
if(de[tp[x]]<de[tp[y]])
swap(x,y);
change(1,1,n,id[tp[x]],id[x],z);
x=f[tp[x]];
}
if(de[x]>de[y])
swap(x,y);
change(1,1,n,id[x]+1,id[y],z);
}
int ask1(int x,int y)
{
int ans=0;
while(tp[x]!=tp[y])
{
if(de[tp[x]]<de[tp[y]])
swap(x,y);
ans+=ask(1,1,n,id[tp[x]],id[x]);
x=f[tp[x]];
}
if(de[x]>de[y])
swap(x,y);
ans+=ask(1,1,n,id[x]+1,id[y]);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
while(1)
{
scanf("%d",&a[++l].op);
if(a[l].op==-1)break;
scanf("%d%d",&a[l].x,&a[l].y);
if(a[l].x>a[l].y)swap(a[l].x,a[l].y);
if(a[l].op==0)
mp[make_pair(a[l].x,a[l].y)]=1;
}
l--;
tarjan(1,1);
for(int i=1;i<=n;i++)
{
for(int j=0;j<v[i].size();j++)
{
int to=v[i][j];
if(era(i,to)||now[i]==now[to])continue;
g[now[i]].push_back(now[to]);
}
}
for(int i=1;i<=l;i++)
{
a[i].x=now[a[i].x];
a[i].y=now[a[i].y];
}//缩点后的新编号
dfs1(1,1);
dfs2(1,1);
build(1,1,n);
for(int i=l;i>=1;i--)//倒着进行循环
{
switch(a[i].op)
{
case 0:
{
add(a[i].x,a[i].y,0);//每遇到一次已删除的边则“复活”
break;
}
case 1:
{
ans[i]=(a[i].x==a[i].y?0:ask1(a[i].x,a[i].y));
break;
}
}
}
for(int i=1;i<=l;i++)//重新按照正确的顺序输出答案
if(a[i].op==1)
printf("%d\n",ans[i]);
return 0;
}