Link Cut Tree

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

定义:

  首先来定义一些量:

  access(x)(或者叫expose(x)):表示访问X点

  Preferred child(偏爱子节点):如果最后被访问的点在X的儿子P节点子树中,那么称P为X的Preferred child,如果一个点被访问,他的Preferred child为null(即没有)。

  Preferred edge(偏爱边):每个点到自己的Preferred child的边被称为Preferred edge。

  Preferred path(偏爱路径):由Preferred edge组成的不可延伸的路径称为Preferred path。

这样我们可以发现一些比较显然的性质,
每个点在且仅在一条Preferred path上,
也就是所有的Preferred path包含了这棵树上的所有的点,
这样一颗树就可以由一些Preferred path来表示(类似于轻重链剖分中的重链),
我们用splay来维护每个条Preferred path,关键字为深度

也就是每棵splay中的点左子树的深度都比当前点小,右节点的深度都比当前节点的深度大

这样的每棵splay我们称为Auxiliary tree(辅助树),
每个Auxiliary tree的根节点保存这个Auxiliary tree与上一棵Auxiliary tree中的哪个点相连
这个点称作他的Path parent(路上祖先)

操作:

expose(x):首先由于preferred path的定义,如果一个点被访问,
那么这个点到根节点的所有的边都会变成preferred edge,
由于每个点只有一个preferred child,所以这个点到根节点路径上的所有的点都会和原来的preferred child断开,
连接到这条新的preferred path上
假设访问x点,那么先将x点旋转到对应Auxiliary tree的根节点,
因为被访问的点是没有preferred child的,所以将Auxiliary tree中根节点(x)与右子树的边断掉,
左节点保留,将这个树的path parent旋转到对应Auxiliary tree的根节点,
断掉右子树,连接这个点与x点,相当于合并两棵Auxiliary tree,
不断地重复这一操作,直到当前X所在Auxiliary tree的path parent为null时停止,表示已经完成当前操作

这里写图片描述

这里写图片描述
find root(x):找到某一点所在树的根节点(维护森林时使用)
只需要expose(X),然后将X节点旋到对应Auxiliary tree的根节点,
然后找到这个Auxiliary tree中最左面的点

cut(x):断掉X节点和其父节点相连的边
首先expose(x),将x旋转到对应Auxiliary tree的根节点,
然后断掉Auxiliary tree中x和左节点相连的边

link(x,y):连接点x到y点上,即让x成为y的子节点
因为x为y的子节点后,
在原x的子树中,x点到根节点的所有的点的深度会被翻转过来,
所以先expose(x),然后在对应的Auxiliary tree中将x旋转到根节点,
然后将子树翻转(splay中的reverse操作),
然后expose(y),将y旋转到对应Auxiliary tree中的根节点,将x连到y就行了。

时间复杂度:
证明expose以及其他操作的时间复杂度是均摊log2N的,
具体证明参考杨哲的论文《QTREE 解法的一些研究》。

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N=1000005;
int n,m,root,cnt;
int mx[N],pre[N],v[N];
int ch[N][2],lazy[N];  //lazy 值的标记 
bool rev[N];  //翻转标记 
int q[N];  //辅助splay 
struct  node{
    int x,y,nxt;
};
node way[N<<1];
int st[N],tot=0;

int get(int bh)
{
    return ch[pre[bh]][0]==bh ? 0:1;
}

void addway(int u,int w)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
    tot++;
    way[tot].x=w;way[tot].y=u;way[tot].nxt=st[w];st[w]=tot;
}

void update(int bh)  //维护最大值 
{
    mx[bh]=max(mx[ch[bh][0]],mx[ch[bh][1]]);
    mx[bh]=max(mx[bh],v[bh]);
    ///也可以维护size 
}

void push(int bh)
{
    int l=ch[bh][0],r=ch[bh][1];
    if (bh&&rev[bh])  //翻转标记 
    {
        if (ch[bh][0]) rev[l]^=1; 
        if (ch[bh][1]) rev[r]^=1;
        rev[bh]^=1;  //下传标记 
        swap(ch[bh][0],ch[bh][1]);
    }
    if (flag[bh])  //维护值 
    {
        if (l)  //有左儿子 
        {
            lazy[l]+=lazy[bh]; mx[l]+=lazy[bh]; v[l]+=lazy[bh];
        }
        if (r)  //有右儿子 
        {
            lazy[r]+=lazy[bh]; mx[r]+=lazy[bh]; v[r]+=lazy[bh];
        }
        lazy[bh]=0;
    } 
}

int isroot(int bh)  //没有爸爸了 
{
    return ch[pre[bh]][0]!=bh&&ch[pre[bh]][1]!=bh;
}

void rotate(int bh)  //正常的rotate 
{
    int fa=pre[bh];
    int grand=pre[fa];
    int wh=get(bh);
    if (!isroot(fa)) ch[grand][ch[grand][0]==fa ? 0:1]=bh;  //!isroot(fa)
    ch[fa][wh]=ch[bh][wh^1];
    pre[ch[fa][wh]]=fa;
    ch[bh][wh^1]=fa;
    pre[fa]=bh;
    pre[bh]=grand;
    update(fa);
    update(bh);
}

void splay(int bh)
{
    int top=0;
    q[++top]=bh;
    for (int i=bh;!isroot(bh);i=pre[i])   //先加入队列中   !isroot(bh)
        q[++top]=pre[i];  //pre[i]
    while (top) push(q[top--]);  //都先进行push 
    for (int fa;!isroot(bh);rotate(bh))   //!isroot(bh)
        if (!isroot(fa=pre[bh]))
           rotate(get(bh)==get(fa)? fa:bh);      
} 

void expose(int x)  //查询x 
{
    int t=0;
    while (bh)  //while(bh)
    {
        splay(bh);
        ch[bh][1]=t;  //
        t=bh;
        bh=pre[bh];
    }
}

void makeroot(int x)
{
    expose(x);
    splay(x);    //转到根 
    rev[x]^=1;   //深度翻转 
}

void link(int x,int y)  //x-->y
{
    makeroot(x);
    fa[x]=y;
    splay(x);   ///
}

void cut(int x,int y)
{
    makeroot(x);
    expose(y); spaly(y);
    ch[y][0]=pre[x]=0;  ///
    update(y);
}

void find(int x)  //寻找x所在的辅助树中对应的原树的根(深度最小) 
{
    expose(x);
    spaly(x);
    while (ch[x][0]) x=ch[x][0];
    return x; 
}

void add(inr x,int y,int vv)
{
    makeroot(x);
    expose(y);
    splay(y);
    lazy[y]+=v;
    mx[y]+=v;
    v[y]+=vv;
}
原文地址:https://www.cnblogs.com/wutongtong3117/p/7673563.html