P2542 【[AHOI2005]航线规划】

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;

}

巴特西

P2542 【[AHOI2005]航线规划】

最新文章

热门文章