LCT

一个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解法的一些研究

巴特西

LCT

最新文章

热门文章