蒟蒻的LCT解读(1)

　　前段时间本蒟蒻自学了一下LCT，但是网上的很多资料并不很全，而且作为一个数组选手，我看指针代码真的很麻烦，所以就在这里写一篇数组选手能看懂的代码。

LCT的初步了解

LCT全称Link_Cut_Tree,中文名动态树,Tarjan大爷的发明专利。

动态树是一类要求维护森林的连通性的题的总称，这类问题要求维护某个点到根的某些数据，支持树的切分，合并，以及对子树的某些操作。其中解决这一问题的某些简化版（不包括对子树的操作）的基础数据结构就是LCT(link-cut tree)。

　　LCT的大体思想类似于树链剖分中的轻重链剖分，轻重链剖分是处理出重链来。由于重链的定义和树链剖分是处理静态树所限，重链不会变化，变化的只是重链上的边或点的权值，由于这个性质，我们用线段树来维护树链剖分中的重链，但是LCT解决的是动态树问题（包含静态树），所以需要用更灵活的splay来维护这里的“重链”。

　　看完之后我们知道，LCT和静态的树链剖分很像。怎么说呢？这两种树形结构都是由若干条长度不等的“重链”和“轻边”构成（名字可以不同，大概就是这个意思），“重链”之间由”轻边”连接。就像这样：

　　

　　较粗的就是重边。

与树链剖分的不同：

看到这里，我想很多人会问，那写树链剖分不就好了，写什么LCT呀！

　　LCT和树链剖分不同的是，树链剖分的链是不会变化的，所以可以很方便的用线段树维护。但是，既然是动态树，那么树的结构形态将会发生改变，所以我们要用更加灵活的维护区间的结构来对链进行维护，不难想到Splay可以胜任。如何分离树链也是保证时间效率的关键（链的数量和长度要平衡），树链剖分的“重儿子”就体现了前人博大精深的智慧。

　　在这里解释一下为什么要把树砍成一条条的链：我们可以在logn的时间内维护长度为n的区间（链），所以这样可以极大的提高树上操作的时间效率。在树链剖分中，我们把一条条链放到线段树上维护。但是LCT中，由于树的形态变化，所以用能够支持合并、分离、翻转等操作的Splay维护LCT的重链（注意，单独一个节点也算是一条重链）。

　　这时我们注意到，LCT中的轻边信息变得无法维护。为什么呢？因为Splay只维护了重链，没有维护重链之间的轻边；而LCT中甚至连根都可以不停的变化，所以也没法用点权表示它父边的边权（父亲在变化）。所以，如果在LCT中要维护边上信息，个人认为最方便的方法应该是把边变成一个新点和两条边。这样可以把边权的信息变成点权维护，同时为了不影响，把真正的树上节点的点权变成0，就可以用维护点的方式维护边。

关于一些定义：

struct link_cut_tree {

	int father;//父亲节点

	int ch[2];//左右儿子

	bool reverse;//区间反转标记

	bool is_root;//是不是所在splay的根

}tree[maxn];

巴特西

LCT解读（1）

蒟蒻的LCT解读(1)

LCT的初步了解

与树链剖分的不同：

关于一些定义：

最新文章

热门文章