[模板]Link-Cut-Tree

LCT模板。

Orz了一下大佬的板子

Orz

UPD(10.19):好像理解LCT了。。。

LCT相当与把一个树剖分，分成实边和虚边，对于每一个实链用一个splay维护一下它的深度，然后当你想进行操作的时候就用splay灵活的变更它的深度与父子关系。

其中实边接的两个点父子相认，就是父节点承认有这个子结点，而虚边父节点就不承认有这个子节点。

其中核心操作access，是把x->root路径上的所有边标记成实边，路径上的点项链的其它边标记成虚边。具体实现是从x向上，一直往上跳fa，在splay上断掉当前节点的右儿子，然后接上x->root路径上的它的下一个。

makeroot(x)就是把x作为它的根，这样的话我们可以先access(x)，意思是把root->x上的路径变成实的，然后splay(x)，再给x打个rev标记，意思是把x的深度调到最浅。

link(x,y)就是先把x弄成根，再在x和y之间连一条虚边。

cut(x,y)就是把x弄成根，access了y，这样的话实链上就只有x和y了，就可以直接断了。

对于这里面的splay的isroot操作，当该节点不是父节点的儿子的时候就说明走到了这个实链的顶端了。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int N=3e5+5;

int n,m,p[N],sum[N],fa[N],ch[N][2],stk[N];

bool rev[N];

void pushup(int x) {sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^p[x];}

bool ck(int x) {return x==ch[fa[x]][1];}

void pushdown(int x) {if(rev[x]) rev[ch[x][0]]^=1,rev[ch[x][1]]^=1,rev[x]^=1,swap(ch[x][0],ch[x][1]);}

bool isroot(int x) {return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}

void rotate(int x) {

	int old=fa[x],oldf=fa[old];

	bool chk=ck(x);

	if(!isroot(old)) ch[oldf][ck(old)]=x;

	ch[old][chk]=ch[x][chk^1];

	fa[ch[old][chk]]=old;

	ch[x][chk^1]=old;

	fa[old]=x;

	fa[x]=oldf;

	pushup(old);

	pushup(x);

}

void splay(int x) {

	int top=0;

	stk[++top]=x;

	for(int i=x; !isroot(i); i=fa[i]) stk[++top]=fa[i];

	for(int i=top; i; i--) pushdown(stk[i]);

	for(int f; !isroot(x); rotate(x)) if(!isroot(f=fa[x])) rotate(ck(x)==ck(f)?f:x);

}

void access(int x) {for(int t=0; x; t=x,x=fa[x]) splay(x),ch[x][1]=t,pushup(x);}

void makeroot(int x) {access(x),splay(x),rev[x]^=1;}

int find(int x) {access(x),splay(x);while(ch[x][0])x=ch[x][0];return x;}

void link(int x,int y) {makeroot(x),fa[x]=y;}

void cut(int x,int y) {

	makeroot(x);access(y);splay(y);

	if(ch[x][0]||ch[x][1]||fa[x]!=y||ch[y][ck(x)^1])return;

	ch[y][0]=fa[x]=0;

}

void change(int x,int y) {p[x]=y,access(x),splay(x);}

int query(int x,int y) {makeroot(x),access(y),splay(y);return sum[y];}

int main() {

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

	for(int i=1; i<=n; i++) scanf("%d",&p[i]);

	for(int i=1,opt,x,y; i<=m; i++) {

		scanf("%d%d%d",&opt,&x,&y);

		switch(opt) {

			case 0:printf("%d\n",query(x,y));break;

			case 1:if(find(x)!=find(y)) link(x,y);break;

			case 2:if(find(x)==find(y)) cut(x,y);break;

			case 3:change(x,y);break;

		}

	}

}

巴特西

[模板]Link-Cut-Tree

最新文章

热门文章