题解 P2542 【[AHOI2005]航线规划】
Haworthia
2019-10-04 22:04:48
这是蒟蒻国庆集训时听的题，讲课的巨佬只给了思路，大致如下：
1、环上的边一定不是关键边。
2、时间反演，逆向处理操作，变成插入边和询问。
3、搞出来一棵树。
4、处理操作，如果我们在v[i]和u[i]之间加入了一条边，那么树上v[i]到u[i]之间的所有边都标记为不是关键边。询问，就是看树上v[i]到u[i]的路径上有多少条边还没有被标记。用树剖维护即可。
以上，和其他发题解的大佬的思路都是差不多的。蒟蒻这里主要是说一些细节，自己错误的地方（自己改得快要崩溃的时候就希望有这样的提示啊）
1、我第一次提交就MLE了。MLE一般就是两种：数组过大（这题显然不是），死循环/无限递归导致爆栈。我自己的情况是出在搞出一颗树，也即树剖的第一次dfs的时候。
分析：题目中给了m条边，然后删去了若干条。我们要时间反演，把他们都删掉，再加回来。**都删掉以后，剩下的边肯定是多于n-1条的。但我直接默认剩下刚好是一颗树，直接dfs，于是死循环。**（为啥是MLE而不是TLE呢？我也不知道）
改正：见代码注释。
2、然后就WA了。实在改不出来，于是参考题解，才发现和上一个错因一模一样。
分析：我还是默认剩下是一颗树（怎么会有这么蠢的人），相当于多删去了很多边。这些**被我误删的边，全部都要加回来**，即是dfs3。
改正：见代码注释。
~~其实WA了十多遍这种事怎么可能告诉别人呢~~，各种稀奇古怪的问题，主要在是搞出一颗树时，这一点我的思路一开始就是错的
AC code：
```
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rint register int
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long ll;
const int N=40000+10,M=100000+10;
int n,m,a,b,x,y,z,bnt,cnt,dnt,tot;
int ans[N],head[N],siz[N],fa[N],dep[N],son[N],id[N],top[N],tr[N<<2],lazy[N<<2];
struct node
{
int op,a,b;
}q[N];
struct mode
{
int v,next,des;
}e[M<<1];
inline void adde(int u,int v)
{
e[++cnt]=(mode){v,head[u]};
head[u]=cnt;
}
inline void read(int &x)
{
x=0;
int f=1;
char s=getchar();
while(s<'0'||s>'9')
{
if(s=='-')
f=-1;
s=getchar();
}
while(s>='0'&&s<='9')
{
x=(x<<1)+(x<<3)+s-'0';
s=getchar();
}
x*=f;
}
inline void pushup(int rt)
{
tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
inline void pushdown(int rt)
{
lazy[rt<<1]=lazy[rt<<1|1]=1;
tr[rt<<1]=tr[rt<<1|1]=lazy[rt]=0;
}
void build(int l,int r,int rt)
{
if(l==r)
{
tr[rt]=1;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
tr[rt]=0,lazy[rt]=1;
return;
}
if(lazy[rt])
pushdown(rt);
int m=(l+r)>>1;
if(L<=m)
update(L,R,lson);
if(m<R)
update(L,R,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
return tr[rt];
if(lazy[rt])
pushdown(rt);
int m=(l+r)>>1,sum=0;
if(L<=m)
sum+=query(L,R,lson);
if(m<R)
sum+=query(L,R,rson);
return sum;
}
void dfs1(int u,int va)
{
fa[u]=va;
siz[u]=1;
dep[u]=dep[va]+1;
for(rint i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(siz[v]||e[i].des)//改进1：如果siz[v]不为0，则v已经被遍历过了（相当于一个vis数组的功能）
continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v])
son[u]=v;
}
}
void dfs2(int u,int anc)
{
id[u]=++bnt;
top[u]=anc;
if(!son[u])
return;
dfs2(son[u],anc);
for(rint i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(fa[v]!=u||v==son[u]||e[i].des)
continue;
dfs2(v,v);
}
}
inline void mark(int a,int b)
{
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])
swap(a,b);
update(id[top[a]],id[a],1,n,1);
a=fa[top[a]];
}
if(dep[a]<dep[b])
swap(a,b);
update(id[b]+1,id[a],1,n,1);
}
void dfs3(int u)//改进2：被误删的边，再时间反演之前全部补回来
{
for(rint i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(e[i].des)
continue;
if(fa[v]==u)
dfs3(v);
else
if(dep[u]<dep[v])
mark(u,v);
}
}
int main()
{
// freopen("1.in","r",stdin);
read(n),read(m);
memset(head,-1,sizeof head);
for(rint i=1;i<=m;++i)
{
read(a),read(b);
adde(a,b),adde(b,a);
}
for(;;)
{
read(x);
if(x==-1)
break;
read(y),read(z);
q[++dnt]=(node){x,y,z};
if(x)
continue;
for(rint i=head[y];~i;i=e[i].next)
if(e[i].v==z)
{
e[i].des=1;
break;
}
for(rint i=head[z];~i;i=e[i].next)
if(e[i].v==y)
{
e[i].des=1;
break;
}
}
dfs1(1,0);
dfs2(1,1);
build(1,n,1);
dfs3(1);
for(rint i=dnt;i>=1;--i)
{
a=q[i].a,b=q[i].b;
if(!q[i].op)
mark(a,b),ans[i]=-1;
else
{
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])
swap(a,b);
ans[i]+=query(id[top[a]],id[a],1,n,1);
a=fa[top[a]];
}
if(dep[a]<dep[b])
swap(a,b);
ans[i]+=query(id[b]+1,id[a],1,n,1);
}
}
for(rint i=1;i<=dnt;++i)
if(ans[i]!=-1)
printf("%d\n",ans[i]);
return 0;
}
```