LCT(Link-Cut Tree)是一种维护动态森林的数据结构,它类似于静态的树链剖分,但区别在于它是动态的,而且重儿子的定义也与树链剖分的不同,下面就来看一下一些LCT基本的存储变量。
偏爱的儿子:类似于树链剖分中的重儿子,但它并没有重儿子的约束条件,也就是说,它不必满足儿子节点个数为所有儿子中最大的这个条件,它可以是任意的一个儿子。
偏爱的边:定义与重边相同,即连接两个偏爱的儿子的边为偏爱的边。
偏爱的链:定义与重链相同,即一条链中所有的点都为偏爱的儿子节点的最长链即为偏爱的链。
Path-Parent[u]:类似于pre[top[u]],即该节点所在的偏爱的链的最高点的父亲。