Article From:https://www.cnblogs.com/yangsongyi/p/9967609.html

LctTalking about

1.Understanding of LCT

​  First, you need to know what $lct $is. The full name of $lct $is $link-cut-tree$. From the full name, we can see that the data structure is a problem of maintaining trees, and can support the operation of edge-breaking. LCT $is a dynamic tree that can handle dynamic forest problems.It also supports query and modification.

2.Pre knowledge

  Before learning about $lct $we recommend learning about tree chain splitting and tree chain splitting nested segment tree, because the idea of $lct $is similar to that of tree chain splitting nested segment tree, and tree chain splitting nested segment tree maintains static tree and is easy to implement. And in the code implementation of $lct $we’re going to use $splay $this.A little bit of knowledge, so I suggest learning it.

3.$lct$Explanation

​  Let’s first look at the tree chain split nested tree, which is to build the whole tree first. We directly cut the tree on the constructed tree, and build the line segment tree on the tree dissection order, just do it indiscriminately on the line segment tree. How can we turn a static tree into a dynamic tree? Because the segment tree is static and cannot support insertion, soWe need to change the data structure we use, and we need to change the segment tree to $splay$.

​  In $lct $we need to explain eight operations. Before explaining these operations, we need to know some nouns and their meanings.

​  1) Auxiliary Tree and Virtual Subtree: We use $splay $in the algorithm of $lct $, and this $splay $is basically similar to the use of the tree in the middle of the tree section. The $splay $is used to maintain the chain on the tree. One chain is a $splay.$. What these $splay dollars make up is called an auxiliary tree. The key to maintain the auxiliary tree is the depth of the current node, that is, the depth of all points in the subtree of the right son of a node on $splay $is smaller than the depth of the current point, and vice versa. But we use $s.Play $maintains the chain. How do these $splay dollars come together? We record the father of the current node when maintaining $splay $and there is no father at the root node of the entire $splay $when we point the father of the root to the top of the whole chain in the original tree.Father is good. This is what we call the father at the top of the chain in the original tree has a virtual sub-tree, which is the whole chain of $splay $.

​  After knowing the above two nouns, let’s explain the operation.

​  1) $Splay$:This operation is to rotate the current node to the root of $splay $where the current node is located. This operation needs to be implemented with $rotate $and the two functions are not much different from the normal $splay $except for the root, which is determined by the father of the current node.Whether the son is not equal to himself, if it is the root, and vice versa.

bool check(int p) {return son[fa[p]][1]==p;}
bool isroot(int p) {return son[fa[p]][0]!=p&&son[fa[p]][1]!=p;}
void rotate(int p)
{
	int tmp1=fa[p],tmp2=fa[tmp1],tmp3=check(p);
	fa[son[tmp1][tmp3]=son[p][tmp3^1]]=tmp1,fa[p]=tmp2;
	if(!isroot(tmp1)) son[tmp2][check(tmp1)]=p;
	fa[son[p][tmp3^1]=tmp1]=p,pushup(tmp1),pushup(p);
}
void splay(int p)
{
	update(p);
	for(int i;i=fa[p],!isroot(p);rotate(p))
		if(!isroot(i)) rotate(check(p)==check(i)?i:p);
}

  2) $Access$:This operation turns the chain from the current node to the root of the auxiliary tree where the current node is located into a $splay$, and the code is easy to understand.

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

  3) $Makeroot$:This operation is to change the current node into the root of the auxiliary tree where the current node is located. Obviously, this operation is to first $Access $for the current node and then $Splay $for the current node. Because we want to ensure time complexity, we will now

void makeroot(int p)
{
    access(p),splay(p),swap(son[p][0],son[p][1]),rev[p]^=1;
}

  4) $Update$:The function of this function has been mentioned above.

void pushdown(int p)
{
	if(!rev[p]) return;
	swap(son[son[p][0]][0],son[son[p][0]][1]);
	swap(son[son[p][1]][0],son[son[p][1]][1]);
	rev[son[p][0]]^=1,rev[son[p][1]]^=1,rev[p]=0;
}
void update(int p)
{
    if(!isroot(p)) update(fa[p]);pushdown(p);
}

  5) $Pushup$:This operation is used to count the answers, similar to the $pushup $on the line segment tree.

void pushup(int p)
{
    if(p) size[p]=1+size[son[p][1]]+size[son[p][0]];
}

  6) $Link$:This operation is to connect the $x, y $together. We need to start with $Makeroot (x)$and $Makeroot (y)$. So we can directly change the auxiliary tree with $fa [x]= y$, so that we can change the auxiliary tree with $x $as the root into the auxiliary tree with $y $as the root.The virtual sub-tree of the assistant tree is solved in this way.

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

  7) $Cut$:This operation is to break the edge and disconnect the edges connected by $x and $y. Let’s start with $Makeroot (x)$, and $Access (y), Splay (y)$, and then the left son of $y is $x$, so all we need is $son [y] [0] = FA [x] = 0.Just $

void cut(int x,int y)
{
    makeroot(x),access(y),splay(y),son[y][0]=fa[x]=0;
}

  8) $Find$:This operation is used to find who is the root of the current node in the auxiliary tree.

int find(int x)
{
    access(x),splay(x);
    while((son[x][0]&&rev[x]==false)||(son[x][1]&&rev[x])) pushdown(x),x=son[x][0];
    return x;
}

  To integrate, here are the following templates:

bool check(int p) {return son[fa[p]][1]==p;}
bool isroot(int p) {return son[fa[p]][0]!=p&&son[fa[p]][1]!=p;}
void pushdown(int p)
{
	if(!rev[p]) return;
	swap(son[son[p][0]][0],son[son[p][0]][1]);
	swap(son[son[p][1]][0],son[son[p][1]][1]);
	rev[son[p][0]]^=1,rev[son[p][1]]^=1,rev[p]=0;
}
void pushup(int p) {if(p) size[p]=1+size[son[p][1]]+size[son[p][0]];}
void update(int p) {if(!isroot(p)) update(fa[p]);pushdown(p);}
void rotate(int p)
{
	int tmp1=fa[p],tmp2=fa[tmp1],tmp3=check(p);
	fa[son[tmp1][tmp3]=son[p][tmp3^1]]=tmp1,fa[p]=tmp2;
	if(!isroot(tmp1)) son[tmp2][check(tmp1)]=p;
	fa[son[p][tmp3^1]=tmp1]=p,pushup(tmp1),pushup(p);
}
void splay(int p)
{
	update(p);
	for(int i;i=fa[p],!isroot(p);rotate(p))
		if(!isroot(i)) rotate(check(p)==check(i)?i:p);
}
void access(int p) {for(int t=0;p;t=p,p=fa[p]) splay(p),son[p][1]=t,pushup(p);}
void makeroot(int p) {access(p),splay(p),swap(son[p][0],son[p][1]),rev[p]^=1;}
void link(int x,int y) {makeroot(x),makeroot(y),fa[x]=y,ord[y]+=size[x];}
void cut(int x,int y) {makeroot(x),access(y),splay(y),son[y][0]=fa[x]=0;}
Link of this Article: Lct discussion

Leave a Reply

Your email address will not be published. Required fields are marked *