一个LCT看了一天了,但是很多地方还是理解的很模糊,简单谈一下理解。

LCT支持的是对于森林的分裂、合并,以及查询节点的连通性等操作。

对于这片森林来说,它是由一坨树组成的,对于每一棵树,我们采用类似于树链剖分的方法,把它分割成若干条链,称为树链。

对于每条树链,维护它的顶点和父亲节点(就是顶点的父亲),并且用splay维护这个结构。

下面来定义几个关于节点u的东西:

  fa: v的父亲节点

  fpath: v所在的树链的父亲

  zson:v的子树中最后一次被access的点,如果是他自己,则没有zson

下面说几个操作:

  ①access:这是LCT中最基本的操作,它的作用是将v到根节点形成一条新的树链。

    操作结果:将v到根节点扫一遍,这样的话,从v到根节点会形成一条新的树链,且如果这条树链经过的某个节点u不是他父亲的zson,由于fa[u]的zson将变成u,所以,pa[u]原来的树链不再包含fa[u]及其以上的节点。

    操作过程:如果了节点v,那么他的zson就会消失,所以先将v转到它所在的splay的根节点,然后将右子树(对应的zson)分离,并把新得到的树链的fpath赋值为v。如果v所属的树链不包含根节点,设树链的fpath为u,就把u旋转到splay的根节点上,把v练到u的右子树上,那么u原来右子树的fpath设置为u,这样一来,便可到达根节点。

  ②cut:这个操作和splay的删除操作差不多,先把x转到splay的根节点,然后把y转到根节点,这样x就在y的左孩子的位置上,然后把c[y][0]和fa[x]清零。(不是很明白为什么要rev一下,听z爷说是要把x转移到它所在的树链的顶端,貌似有些道理。)

  ③join:将u转到根节点,然后重新赋值fa[u]即可。

参考论文:QTREE解法的一些研究

05-08 15:08