题解 P2542 【[AHOI2005]航线规划】
树链剖分+离线树转图
观察题面,我们发现关键边就是桥,如果没有删边操作,就是一道tarjan裸题了。虽然我们可以一边删边一边更新tarjan,但时间复杂度应该过不了。所以我们要换一种思路。
我们注意到题中一句话:"保证联通"。如果我们不断删边,又保证联通,那么整张图最后会变成什么样呢?明显会变成一棵树。树就是好东西了,很多数据结构都能在树上用。而且我们发现树上的边都是关键边,,所以我们可以先建一棵树,再在树上加边建图。
我们可以明显发现,只要在树上任意两点之间加了一条边就会形成一个环,而对于环上的边显然都不会是关键边。因为树上两点间路径确定,形成环后该路径上所有边就都不为关键边了,所以自然想到将整棵树的边权置为1,每次对于(u,v)加边就将u到v的路径上的所有边边权改为0。
边权转点权,树链剖分实现。查询就直接查询u到v路径上还有多少边边权为1就行了。
然后就是删边操作,删掉一条边又保证联通,显然只能删环上的边,即每次删边后关键边数量一定不减,(假设删边(u,v))若我们每次在u到v的路径上加1,显然无法最优,因为对于u到v路径上的边,不一定删掉(u,v)这条边就一定会让它变成关键边,有可能它还属于别的环。所以我们可以反向考虑,所有要删掉的边都先不加,相当于默认全部删完了,倒序查询询问后再一条一条加回去,这样就可以避免删边操作了。
离线所有操作再倒序实现。
当然删边并不一定会断掉所有环,还有的边连在树上形成环。所以在建树时用并查集维护保证只建出一棵树,再把没加但未来不会删掉的边用成环情况处理。
代码实现细节见代码。
#include <map>
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
struct edge{
int v,next;
}e[60001];
struct node{
int t,a,b;
}dt[40001];//存查询,删边操作
int cnt,tot,head[30001],dep[30001],fa[30001],siz[30001],son[30001],top[30001],id[30001],dfn[30001],low[30001],x[100001],y[100001],add[120005],sum[120005];
bool vis[100001];//记录边是否在树中
map<pair<int,int>,bool> ma;//记录u到v的边会不会删
inline void adde(int u,int v)
{
e[++cnt]=(edge){v,head[u]};
head[u]=cnt;
}
inline int findf(int x)
{
return fa[x]==x?x:fa[x]=findf(fa[x]);
}
inline void find(int u)//树剖模板不解释
{
siz[u]=1;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v!=fa[u])
{
fa[v]=u;
dep[v]=dep[u]+1;
find(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
}
inline void dfs(int u,int fat)
{
top[u]=fat;
id[dfn[u]=++tot]=u;
if(son[u])dfs(son[u],fat);
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v!=son[u]&&v!=fa[u])dfs(v,v);
}
low[u]=tot;
}
inline void pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
inline void pushdown(int rt,int m)
{
if(~add[rt])
{
add[rt<<1]=add[rt<<1|1]=add[rt];
sum[rt<<1]=add[rt]*(m-(m>>1));
sum[rt<<1|1]=add[rt]*(m>>1);
add[rt]=-1;
}
}
inline void build(int l,int r,int rt)//线段树初始赋值全为1
{
add[rt]=-1;
if(l==r)
{
sum[rt]=1;
return;
}
int m=l+r>>1;
build(lson);
build(rson);
pushup(rt);
}
inline void update(int L,int R,int c,int l,int r,int rt)//线段树要建成区间赋值的类型
{
if(L<=l&&r<=R)
{
add[rt]=c;
sum[rt]=c*(r-l+1);
return;
}
pushdown(rt,r-l+1);
int m=l+r>>1;
if(L<=m)update(L,R,c,lson);
if(m<R)update(L,R,c,rson);
pushup(rt);
}
inline int query(int L,int R,int l,int r,int rt)//线段树查询不解释
{
if(L<=l&&r<=R)return sum[rt];
pushdown(rt,r-l+1);
int m=l+r>>1,ret=0;
if(L<=m)ret+=query(L,R,lson);
if(m<R)ret+=query(L,R,rson);
return ret;
}
int main()
{
memset(head,-1,sizeof head);
int n=read(),m=read();
for(int i=1;i<=m;++i)//记边
{
x[i]=read();
y[i]=read();
}
int tim=0;
while(1)//离线 处理
{
int t=read();
if(!(~t))break;
int a=read(),b=read();
dt[++tim]=(node){t,a,b};
if(!t)ma[make_pair(a,b)]=ma[make_pair(b,a)]=1;//要删掉的边先不建
}
for(int i=1;i<=n;++i)
fa[i]=i;
for(int i=1;i<=m;++i)
{
int u=findf(x[i]),v=findf(y[i]);
if(!ma[make_pair(x[i],y[i])]&&fa[u]!=v)//建树,用并查集维护是否成树
{
fa[u]=v;
adde(x[i],y[i]);
adde(y[i],x[i]);
vis[i]=1;//记录边已加入
}//这样建树就会保证只生成一棵树,之后就可以直接加边成环,不需要像其他的做法一样修改树剖的dfs处和dfs3次。
}
memset(fa,0,sizeof fa);
find(1);
dfs(1,1);
build(1,n,1);
for(int i=1;i<=m;++i)
if(!vis[i]&&!ma[make_pair(x[i],y[i])])//边未加入树中且未来不会被删加入图中成环处理
{
int a=x[i],b=y[i];
while(top[a]!=top[b])
{
if(dep[top[a]]>dep[top[b]])swap(a,b);
update(dfn[top[b]],dfn[b],0,1,tot,1);
b=fa[top[b]];
}
if(dep[a]>dep[b])swap(a,b);
update(dfn[a]+1,dfn[b],0,1,tot,1);
}
stack<int> q;
for(int i=tim;i;--i)//倒序处理操作
{
int ans=0,t=dt[i].t,a=dt[i].a,b=dt[i].b;
while(top[a]!=top[b])
{
if(dep[top[a]]>dep[top[b]])swap(a,b);
if(t)ans+=query(dfn[top[b]],dfn[b],1,tot,1);
else update(dfn[top[b]],dfn[b],0,1,tot,1);
b=fa[top[b]];
}
if(dep[a]>dep[b])swap(a,b);
if(t)q.push(ans+query(dfn[a]+1,dfn[b],1,tot,1));
else update(dfn[a]+1,dfn[b],0,1,tot,1);
}
while(!q.empty())//因为是倒序处理操作,所以答案要倒序输出
{
printf("%d\n",q.top());
q.pop();
}
return 0;
}我是蒟蒻