P2542 【[AHOI2005]航线规划】
一个无向图，m个操作
- 删去一条边
- 给定两个点，求有多少边使得如果这条边不存在，给定的两个点不连通
一般这种删边的题目，考虑逆序加边处理
在删完的图中，任意找出一棵生成树，对它进行树链剖分
然后需要把不再这颗生成树中但实际上没被删去的边加回来，当边\((u,v)\)被加回时，\((u,v)\)原本在生成树上的路径就都不是关键航线了（因为\((u,v)\)间已经有了至少两条道路能走）
在加每次操作中涉及的边也是一样
在最初那棵生成树中，每两个点的路径都是唯一的所以每条边都是关键航线，因此在建树时每个点权值赋为1，当它因为有的边被加会而不再关键时就设为0，用线段树维护就行
然后愉快0分
我在求生成树的时候，是和树剖的第一遍dfs一起进行的，但没有单独开vis数组，判断是否访问的时候直接判断if(fa[v])，但1号点（根）的父亲为0，所以就愉快TLE+MLE
改完以后发现10分
忘记pushup这种事肯定不能说出来。。
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#define R register
#define EN std::puts("")
#define LL long long
inline int read(){
int x=0,y=1;
char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n,m;
std::map<int,int>map;
int etot=1,to[200006],nex[200006],fir[30006];
int deleted[200006],ontree[200006];
int fa[30006],deep[30006],size[30006];
int top[30006],dfn[30006],dfscnt,son[30006];
struct tr{
tr *ls,*rs;
int tag,sum;
}dizhi[60007],*root=&dizhi[0];
int tot;
int qc[100006],qx[100006],qy[100006],qtot;
int ans[100006],anstot;
inline void swap(int &x,int &y){x^=y;y^=x;x^=y;}
inline void add(int u,int v){
to[++etot]=v;
nex[etot]=fir[u];fir[u]=etot;
map[u*(n+1)+v]=etot;
}
void dfs1(int u,int fat){
fa[u]=fat;deep[u]=deep[fat]+1;size[u]=1;
for(R int v,i=fir[u];i;i=nex[i])if(!deleted[i]){
v=to[i];
if(fa[v]||v==1) continue;
ontree[i]=1;
dfs1(v,u);size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topnow){
top[u]=topnow;dfn[u]=++dfscnt;
if(!son[u]) return;
dfs2(son[u],topnow);
for(R int v,i=fir[u];i;i=nex[i])if(ontree[i]){
v=to[i];
if(!dfn[v]) dfs2(v,v);
}
}
void build(tr *tree,int l,int r){
if(l==r) return tree->sum=1,void();
int mid=(l+r)>>1;
tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
build(tree->ls,l,mid);build(tree->rs,mid+1,r);
tree->sum=r-l+1;
}
inline void pushdown(tr *tree){
if(tree->tag){
tree->ls->tag=tree->rs->tag=1;
tree->ls->sum=tree->rs->sum=0;
tree->tag=0;
}
}
void change(tr *tree,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tree->tag=1,tree->sum=0,void();
int mid=(l+r)>>1;
pushdown(tree);
if(ql<=mid) change(tree->ls,l,mid,ql,qr);
if(qr>mid) change(tree->rs,mid+1,r,ql,qr);
tree->sum=tree->ls->sum+tree->rs->sum;
}
int qsum(tr *tree,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tree->sum;
int mid=(l+r)>>1,ret=0;
pushdown(tree);
if(ql<=mid) ret=qsum(tree->ls,l,mid,ql,qr);
if(qr>mid) ret+=qsum(tree->rs,mid+1,r,ql,qr);
return ret;
}
inline void updata(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
change(root,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
if(dfn[x]!=dfn[y]) change(root,1,n,dfn[x]+1,dfn[y]);
}
inline int sum(int x,int y){
R int ret=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ret+=qsum(root,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
if(dfn[x]!=dfn[y]) ret+=qsum(root,1,n,dfn[x]+1,dfn[y]);
return ret;
}
int main(){
n=read();m=read();
for(R int x,y,i=1;i<=m;i++){
x=read();y=read();
add(x,y);add(y,x);
}
R int x,y,cc,c=read();while(c!=-1){
x=read();y=read();
qc[++qtot]=c;qx[qtot]=x;qy[qtot]=y;
cc=map[x*(n+1)+y];
if(!c) deleted[cc]=deleted[cc^1]=1;
c=read();
}
dfs1(1,0);dfs2(1,1);
build(root,1,n);
for(R int i=1;i<=n;i++){
for(R int j=fir[i];j;j=nex[j])
if(!ontree[j]&&!ontree[j^1]&&!deleted[j]) updata(i,to[j]);
}
for(R int i=qtot;i;i--){
if(qc[i]) ans[++anstot]=sum(qx[i],qy[i]);
else updata(qx[i],qy[i]);
}
for(R int i=anstot;i;i--) std::printf("%d\n",ans[i]);
return 0;
}