[BJOI2014]大融合(Link Cut Tree)

题面

给出一棵树，动态加边，动态查询通过每条边的简单路径数量。

分析

通过每条边的简单路径数量显然等于边两侧节点x,y子树大小的乘积。

我们知道裸的LCT只能维护链的信息，那么怎么维护子树大小呢？我们只需要对于节点x维护x的所有虚儿子的子树大小之和vir。那么查询的时候先split(x,y),这样x到y就成为了实链,其他与x相连的节点都是虚儿子。那么x一侧的子树大小就是vir[x]+1,y一侧的子树大小就是vir[y]+1

考虑虚子树大小如何维护:

首先总的子树大小可以在push_up的时候维护,sz[x]=sz[lson(x)]+sz[rson(x)]+vir[x]+1.相当于把实儿子的子树大小求和，然后加上虚儿子的子树大小之和，再加上本身1

注意到只有access和link操作会影响到vir[x].

//一般LCT的access

void access(int x){

		for(int y=0;x;y=x,x=fa(x)){

			splay(x);

			rson(x)=y;

			push_up(x);

		}

	}

观察access的过程，我们发现原来x的右儿子变成了虚儿子，而y变成了x的实儿子。因此vir要加上原来rson(x)的子树大小，并且减去y的子树大小

void access(int x){

		for(int y=0;x;y=x,x=fa(x)){

			splay(x);

			tree[x].vir+=tree[rson(x)].sz;//原来的实儿子变成虚儿子

			rson(x)=y;

			tree[x].vir-=tree[rson(x)].sz;//原来的虚儿子变成实儿子

			push_up(x);

		}

	}

link操作更简单

//一般LCT的link

void link(int x,int y){

		make_root(x);

		fa(x)=y;

		push_up(y);

}

直接把vir[y]加上sz[x]即可

void link(int x,int y){

		split(x,y);

		fa(x)=y;

		tree[y].vir+=tree[x].sz;

		push_up(y);

}

注意到这里必须split(x,y),因为split之前y在原树中不一定是根，link了以后y的所有祖先的sz数组都是需要更新的.所以要splay(y)，把sz先更新一下。否则会造成一些节点的sz未被更新.

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100000

using namespace std;

typedef long long ll;

struct LCT{

#define lson(x) (tree[x].ch[0])

#define rson(x) (tree[x].ch[1])

#define fa(x) (tree[x].fa)

	struct node{

		int ch[2];

		int fa;

		int sz;//总的子树大小

		int vir;//除了实链外连接到x的点的子树大小

		int revm;

	}tree[maxn+5];

	inline bool is_root(int x){

		return !(lson(fa(x))==x||rson(fa(x))==x);

	}

	inline int check(int x){

		return rson(fa(x))==x;

	}

	void push_up(int x){

		tree[x].sz=tree[lson(x)].sz+tree[rson(x)].sz+1+tree[x].vir;

	}

	void reverse(int x){

		swap(lson(x), rson(x));

		tree[x].revm^=1;

	}

	void push_down(int x){

		if(tree[x].revm){

			reverse(lson(x));

			reverse(rson(x));

			tree[x].revm=0;

		}

	}

	void push_down_all(int x){

		if(!is_root(x)) push_down_all(fa(x));

		push_down(x);

	}

	void rotate(int x){

		int y=fa(x),z=fa(y),k=check(x),w=tree[x].ch[k^1];

		tree[y].ch[k]=w;

		tree[w].fa=y;

		if(!is_root(y)) tree[z].ch[check(y)]=x;

		tree[x].fa=z;

		tree[x].ch[k^1]=y;

		tree[y].fa=x;

		push_up(y);

		push_up(x);

	}

	void splay(int x){

		push_down_all(x);

		while(!is_root(x)){

			int y=fa(x);

			if(!is_root(y)){

				if(check(x)==check(y)) rotate(y);

				else rotate(x);

			}

			rotate(x);

		}

		push_up(x);

	}

	void access(int x){

		for(int y=0;x;y=x,x=fa(x)){

			splay(x);

			tree[x].vir+=tree[rson(x)].sz;//原来的实儿子变成虚儿子

			rson(x)=y;

			tree[x].vir-=tree[rson(x)].sz;//原来的虚儿子变成实儿子

			push_up(x);

		}

	}

	void make_root(int x){

		access(x);

		splay(x);

		reverse(x);

	}

	void split(int x,int y){

		make_root(x);

		access(y);

		splay(y);

	}

	void link(int x,int y){

		split(x,y);

		fa(x)=y;

		tree[y].vir+=tree[x].sz;

		push_up(y);

	}

	void cut(int x,int y){

		split(x,y);

		lson(y)=fa(x)=0;

		push_up(y);

	}

	ll query(int x,int y){

		split(x,y);

//		return 1ll*(tree[x].sz)*(tree[y].sz);

		return 1ll*(tree[x].vir+1)*(tree[y].vir+1);

	}

}T;

int n,m;

int main(){

	int u,v;

	char cmd[2];

	scanf("%d %d",&n,&m);

	for(int i=1;i<=n;i++) T.tree[i].sz=1;

	for(int i=1;i<=m;i++){

		scanf("%s %d %d",cmd,&u,&v);

		if(cmd[0]=='A'){

			T.link(u,v);

		}else{

//			T.cut(u,v);

			printf("%lld\n",T.query(u,v));

//			T.link(u,v);

		}

	}

}

巴特西

[BJOI2014]大融合(Link Cut Tree)

[BJOI2014]大融合(Link Cut Tree)

题面

分析

代码

最新文章

热门文章