「一本通 4.4 例 2」暗的连锁 题解

未分类


题目传送门

题目大意： 给一棵由白边连接的树，里面还有若干条黑边，问有多少种黑边和白边各删除一条后使图不连通的方案。

题解

我这可能是全网绝无仅有的沙雕做法了……

正解： 倍增




+



+


树上差分。

然而我一开始的想法就偏离了正轨……

我的解法：




d


f


s



dfs


序




+



+





s


p


l


a


y



splay





+



+


启发式合并

考虑每一条白边，假如将它删掉之后，再删一条黑边可以使得这棵树不连通，当且仅当这条白边连接的那棵子树中最多只有一条连向子树外的黑边。假如没有连向子树外的黑边，那么删除了这条白边之后，可以再删除任意一条黑边达成一个方案，答案加黑边数量。假如有一条连向子树外的黑边，那么就只能删这条黑边，答案加1。

看到子树，第一时间当然是想到




d


f


s



dfs


序，考虑每一个结点造一棵




s


p


l


a


y



splay


，维护 以他的子树内的结点为起点 的黑边的终点的




d


f


s



dfs


序。处理完儿子之后，将儿子们的




s


p


l


a


y



splay


通过启发式合并与自己的




s


p


l


a


y



splay


合并。

因为




s


p


l


a


y



splay


里面的值是有序的，所以可以利用




d


f


s



dfs


序的性质——一棵子树内的结点的




d


f


s



dfs


序是连续的，将自己的




s


p


l


a


y



splay


内值在自己的子树内的都删掉，然后判断一下自己的




s


p


l


a


y



splay


的大小，统计答案即可。

AC代码（并没有跑得很快）：

#include 
#include 
#include 
using namespace std;
#define maxn 200010

int n,m;
struct edge{int y,next;};
edge white[maxn*2],black[maxn*2];
int first[maxn],fir[maxn];
void buildwhiteroad(int x,int y)
{
	static int len=0;
	white[++len]=(edge){y,first[x]};
	first[x]=len;
}
void buildblackroad(int x,int y)
{
	static int len=0;
	black[++len]=(edge){y,fir[x]};
	fir[x]=len;
}
struct node{
	int x,size;
	node *zuo,*you,*fa;
	node(int c,node *father):x(c),size(1),zuo(NULL),you(NULL),fa(father){}
	friend void ins(int,node *&);
	void check()
	{
		size=1;
		if(zuo!=NULL)size+=zuo->size;
		if(you!=NULL)size+=you->size;
	}
	void go(int l,int r,node *&rt)//将不在区间[l,r]内的点加入到rt这棵树内
	{
		if(x<l||x>r)ins(x,rt);
		if(zuo!=NULL)zuo->go(l,r,rt);
		if(you!=NULL)you->go(l,r,rt);
	}
	node *find(int c)//找到值为c的点
	{
		if(zuo!=NULL&&c<x)return zuo->find(c);
		if(you!=NULL&&c>x)return you->find(c);
		return this;
	}
};
node *root[maxn];
void rotate(node *x)
{
	node *fa=x->fa,*gfa=fa->fa;
	if(fa->zuo==x)
	{
		fa->zuo=x->you;
		if(x->you!=NULL)x->you->fa=fa;
		x->you=fa;
	}
	else
	{
		fa->you=x->zuo;
		if(x->zuo!=NULL)x->zuo->fa=fa;
		x->zuo=fa;
	}
	fa->fa=x;x->fa=gfa;
	if(gfa!=NULL)
	{
		if(gfa->zuo==fa)gfa->zuo=x;
		else gfa->you=x;
	}
	fa->check();x->check();
}
#define witch(x) (x->fa->zuo==x)
void splay(node *x,node *to,node *&rt)//splay基操，不多解释了
{
	while(x->fa!=to)
	{
		if(x->fa->fa==to)rotate(x);
		else if(witch(x)==witch(x->fa))rotate(x->fa),rotate(x);
		else rotate(x);
	}
	if(to==NULL)rt=x;
}
void ins(int c,node *&rt)//往rt这棵树里面加一个值为c的点
{
	if(rt==NULL)
	{
		rt=new node(c,NULL);
		return;
	}
	node *p=rt->find(c);
	if(c<p->x)p->zuo=new node(c,p),splay(p->zuo,NULL,rt);
	else p->you=new node(c,p),splay(p->you,NULL,rt);
}
int dfs[maxn],last[maxn],id=0;
void dfs_1(int x,int fa)//预处理dfs序以及自己子树的dfs序范围
{
	dfs[x]=++id;
	for(int i=first[x];i;i=white[i].next)
	if(white[i].y!=fa)dfs_1(white[i].y,x);
	last[x]=id;
}
node *merge(int l,int r,node *rt1,node *rt2)//启发式合并两棵splay
{
	if(rt1==NULL||rt2==NULL)return rt1==NULL?rt2:rt1;
	if(rt1->size<rt2->size)swap(rt1,rt2);
	rt2->go(l,r,rt1);
	return rt1;
}
int findrank(node *now,int x,int f1)//找到x的排名，f1是一个小的调整，可以结合代码理解
{
	if(now==NULL)return f1;
	if(x==now->x)return (now->zuo!=NULL?now->zuo->size:0)+1;
	if(x<now->x)return findrank(now->zuo,x,f1);
	if(x>now->x)return (now->zuo!=NULL?now->zuo->size:0)+1+findrank(now->you,x,f1);
}
node *findkth(node *now,int x)//找到排名为x的结点
{
	if(now->zuo!=NULL&&x<=now->zuo->size)return findkth(now->zuo,x);
	else
	{
		if(now->zuo!=NULL)x-=now->zuo->size;
		if(x==1)return now;
		else return findkth(now->you,x-1);
	}
}
void del(node *&rt,int l,int r)//将rt这棵树内值在[l,r] 区间内的删掉
{
	int x=findrank(rt,l,1),y=findrank(rt,r,0);
	if(x>y)return;
	if(x==1)
	{
		if(y==rt->size)rt=NULL;
		else
		{
			node *p=findkth(rt,y+1);
			splay(p,NULL,rt);
			p->size-=p->zuo->size;
			p->zuo=NULL;
		}
	}
	else
	{
		if(y==rt->size)
		{
			node *p=findkth(rt,x-1);
			splay(p,NULL,rt);
			p->size-=p->you->size;
			p->you=NULL;
		}
		else
		{
			node *p=findkth(rt,x-1);
			splay(p,NULL,rt);
			p=findkth(rt,y+1);
			splay(p,rt,rt);
			p->size-=p->zuo->size;rt->size-=p->zuo->size;
			p->zuo=NULL;
		}
	}
}
long long ans=0;
void dfs_2(int x,int fa)
{
	for(int i=first[x];i;i=white[i].next)
	{
		int y=white[i].y;
		if(y==fa)continue;
		dfs_2(y,x);
		root[x]=merge(dfs[x],last[x],root[x],root[y]);//与儿子合并
	}
	for(int i=fir[x];i;i=black[i].next)//把以自己为起点的黑边的终点的dfs序加进来
	{
		int y=black[i].y;
		if(dfs[y]<dfs[x]||dfs[y]>last[x])ins(dfs[y],root[x]);
	}
	if(root[x]!=NULL)del(root[x],dfs[x],last[x]);//删掉没用的点
	if(x!=1&&root[x]==NULL)ans+=(long long)m;//统计结果
	else if(x!=1&&root[x]->size<=1)ans++;
}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1,x,y;i<n;i++)
	{
		scanf("%d %d",&x,&y);
		buildwhiteroad(x,y);
		buildwhiteroad(y,x);
	}
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		buildblackroad(x,y);
		buildblackroad(y,x);
	}
	dfs_1(1,0);
	dfs_2(1,0);
	printf("%lld",ans);
}