LCT-学习笔记

· · 个人记录

为什么这种东西要我们自学...

这几天再多做几道LCT的题

LCT尽量少使用findroot操作，如果经常用的话，可以使用并查集。

感谢@FlashHu@自为风月马前卒的博客

LCT是Tarjan爷爷提出的超强算法，复杂度貌似是O(N \log N)，常数很大。

能够解决的问题

1.求LCA

2.求最小生成树

3.维护链上信息：最大最小，链上和等

4.维护连通性

5.优化单纯性算法，在O(mn\log n)的复杂度下求最大流

既然是动态树，当然要支持动态加入、删除边咯。

构造

解决树上问题时，由一种常见操作叫“链剖分”：

在实链剖分时，选择一个儿子作为重儿子，把连接这两个节点的边作为重边，连接其他儿子的边作为轻边。

与前两种剖分不同的是，实链剖分中的重儿子是可以不断变化的，因此在整棵树中的重链和轻链也是在不断变化的，这就需要我们用更灵活一些的数据结构来维护。

我们使用平衡树来维护链上信息，splay最好。我们用splay维护每一条实路径(仅由实边组成的路径)，因为每条实路径都对应一条从根节点出发的链，这样的话路径上每个节点的深度都是不同的，因此在splay中，我们按深度作为关键字，对于一个节点，它的左孩子所对应的原节点深度比它小，右儿子所对应的原节点深度比它大。

但是这样的话，虽然每个节点都包含在了splay中，但是每个splay之间都是独立的，因此我们要考虑如何在各个splay中建立联系， 对于一个节点，假设它有三个儿子，其中最多有一个节点可以和他在一个splay中，另外两个儿子分别属于不同的splay。这里有一个非常巧妙的性质——另外两个儿子在他们所在的子树中一定是深度最小的，因此我们可以让每个splay中的根节点指向splay中 中序遍历编号最小(也就是原树中深度最小)的节点的父亲。

对于一棵这样的树

它的splay树可能长成这个样子

基础操作

具体看那两个人的博客吧。

access

这里以access(n)为例：

我们自底向上执行access，我们对于每一个实链，现将N点的父亲splay到根，然后把父亲的右儿子（儿子的深度比自己大）置为N，直到N为根。

il void access(int x)
{
    for(ri y=0; x; x=fa[y=x])
        splay(x),rs=y,up(x);
}

特地说一下splay操作：

rotate：

一定要特判y是否为根，这样就不要改z的儿子；其他两行正常。记得pushup。

splay：

先自顶向下pushdown，然后正常rotate，但是到根的判断比较特殊。

makeroot

先access(x)，再splay(x)，这时x会成为splay的根节点，且x不含右儿子。但是根节点所在的splay中，根节点没有左儿子，怎么办？翻转左右子树！

findroot

先accexx(x)，然后splay(x)，再不断的往左走，这样就可以找到x所在树的根节点了。

split(x,y)

makeroot(x); access(y); splay(y);

一定要把一个点转到根才能取出整条链的信息！

link

il void link(int x,int y)
{
    makert(x);
    if(findrt(y)!=x) fa[x]=y;
}

cut

il void cut(int x,int y)
{
    makert(x);
    if(findrt(y)==x&&fa[x]==y&&!rs)
    {
        fa[x]=ch[y][0]=0;
        up(y);
    }
}