主题

主题

 
   

LCT对子树信息的维护

  • 扯淡

以前总是以为LCT只能够维护树链信息。

现在长知识了。

总是有很多神犇,出一些 加边+删边+换根+子树查询 的问题。

那么我们拥有了LCT这种强大的数据结构之后,就可以实现了。


  • 定义

我们定义几种儿子:

  1. x的虚儿子:若在LCT中,Fa[y]=x,且y不为xSplay的儿子,那么我们称y为x的一个虚儿子。

  2. x的实儿子:x的Splay的儿子。众所周知,x的实儿子不一定是x在原树上的儿子。

再定义几种信息:

  1. x的“虚儿子信息”:x的所有的虚儿子的“总信息”。

  2. x的“总信息”:x的“虚儿子信息”+x的实儿子的“总信息”+x的信息

(两个玩意相互定义呢……)


  • 查询

如果我们对x做Access操作,那么x的子树信息,就是x的“虚儿子信息”+x的信息。

注意,x的虚儿子的“总信息”包括了x的虚儿子的实儿子的“总信息”。x的虚儿子的实儿子的信息被计入到了x的“虚儿子信息”中,因而被统计到了答案中。

这样做的原理是因为x的虚儿子的实儿子也属于x的子树。

巧妙正在于此。如果并未感受到,我们可以看接下来的维护。


  • 维护“虚儿子信息”

考虑在什么时候“虚儿子信息”会变化。

Access(x)

在Access(x)中我们进行了虚实边的转换。例如下面的代码:

void Access(int x) {

    for(int t=0; x; t=x,x=Fa[x]) {

        Splay(x); Btr[x].s[1]=t;

    }

}

那么应该需要在变化Btr[x].s[1]之前,更新虚儿子的信息,之后再更新总信息。具体来说,把t的信息从“虚儿子信息”扣除,Btr[x].s[1]的信息加入到“虚儿子信息”。

Link(x,y)

对于Link操作,一般是先令x为根,之后Fa[x]=y。

我们发现y以及y的祖先的信息均要变化。所以我们应该也把y置为根。


  • 维护“总信息”

首先在“虚儿子信息”变化的时候,自然都要维护“总信息”。

Splay(x)

在旋转的时候,x的实儿子的“总信息”变化了。所以需要维护“总信息”。


在其他的操作,例如Make_root(x)与flip(x)的操作,x的“虚儿子信息”不变,“总信息”不变。不必任何更新。

这就是处理换根操作的巧妙之处。


一个练习题,可以参考BZOJ 4530

代码如下:

https://code.csdn.net/snippets/2321929

 
 
评论