Link Cat Tree

一、感性定义

所谓连喵树，即一种对森林支持修改，查询，连边，删边等操作的数据结构（姑且算她是吧）。她用一颗颗互相连接的辅助树维护原森林的信息，辅助树相互连接的边叫虚边，辅助树内相互连接的边叫实边

二、关于辅助树和原森林

1.辅助树的点代表的就是原森林的点，一般我们选取splay作为辅助树。

以原树中节点的深度作为二叉排序树的权值。也就是说，如果我们中序遍历splay，得到的节点深度是严格递增的。

附注：这里的“原树”指“原森林”中的一颗树，下同。

2.辅助树维护的是原树中一条链，因为我们已经保证维护了点的深度，所以点在splay中的形态是不定的，splay互相的形态也可能不同

比如对这个这个原树，它本来是这个样子的

我们用辅助树对它进行操作后，它可能是这个样子的（虚线是虚边，颜色相同为一颗splay）

也可能是这个样子的

还可能是这个样子的

总结一下：我们确保splay中的边是真实的边\(^①\)且保证深度满足要求，而splay互相连接的边不一定是真实的边，它只是代表这两个splay有连接

3.边的表示及存储

如果两个点的父子关系是相互的，那么这条边是实边，两个点在一个splay中

如果两个点的父子关系不是相互的，即一个点的父亲的儿子中确没有自己，代表这是一条虚边，表示splay之间有连接

我们发现，只有splay中的根节点可能存在一条虚边。并且如果这条根节点没有虚边，那么就代表这个点是原树的根。

4.换根

为了很好的查询信息，我们需要能够替换原树的根的操作（后面讲）

三、操作与实现

(1)★\(Access(x)\)★

作用：表示将\(x\)向原树根节点打通一条链，并将这条链搞到一颗splay里面

操作：暴力向上找父亲跳（当然跳的是splay），把右儿子置为跳过来的splay并更新信息

Code:

void access(int now)//在辅助树中打通一条到原树的链

{

    for(int las=0;now;las=now,now=fa)

        splay(now),rs=las,updata(now);

}

这个操作是核心，请好好理解

(2)\(evert(x)\)

作用：将\(x\)置为原树的根节点

操作：首先我们把树打通一条链到根，然后\(splay\)到根。为了保证深度越小的点在中序遍历越靠前，我们要像文艺平衡树一样，把区间给翻转，带上标记

Code:

void evert(int now)//将节点提至原树根节点

{

    access(now),splay(now),Reverse(now);//打通，丢上去，翻转

}

(3)\(findroot(x)\)

作用：找到\(x\)所在原树的根

操作：先打通一条链到根，然后splay上去，最左边的节点就是根了

Code:

int findroot(int now)//寻找原树根节点

{

    access(now),splay(now);

    while(ls) now=ls;

    return now;

}

(4)\(split(x,y)\)

这个操作可以不写，为了方便我们才写它

作用：把\(x\)到\(y\)搞成一条路径放在一颗splay里并且\(y\)为splay的根

操作：把\(x\)放到它所在原树的根，然后把\(y\)给splay上去

我们可以不保证它们一定在一颗原树里，当做无效操作即可

Code:

void split(int u,int v)//把链抽进辅助树（可以不在一颗树）

{

    evert(u),access(v),splay(v);//放至根，打通，丢上去

}

(5)\(link(x,y)\)

作用：连接节点\(x\)和节点\(y\)

操作：把\(x\)变成它所在树的根，然后只把\(x\)的父亲改成\(y\)（连虚边）

如果要不保证合法性，加个判断就行

Code:

void link(int u,int v)//连边

{

    evert(u);//搞到根

    if(findroot(v)!=u)//保证不在一颗树

        par[u]=v;//只连了虚边

}

(6)\(cat(x,y)\)

作用：切断节点\(x\)与节点\(y\)之间的边

操作：把\(x\)和\(y\)搞到一颗splay里面，然后断双向边且更新答案。

如果不保证合法性，同样加个判断就行

Code:

void cat(int u,int v)//断边

{

    split(u,v);

    if(ch[v][0]==u)//直接相连

        par[u]=ch[v][0]=0,updata(v);//双向断边注意更新

}

(7)其他

其他除了前两个操作，其他操作基本可以做的更小的常数，但是以上的比较好理解。

还有一些其他的询问操作或者修改操作就因题而异了。

四、与原先splay的不同之处

(1)\(isroot(x)\)

判断节点\(x\)是不是splay的根

Code:

bool isroot(int now)//判断是否为子树的根

{

    return ch[fa][0]==now||ch[fa][1]==now;

}

(2)旋转时

旋转时不要连多了

因为大家旋转可能写的都不一样，所以就不放代码了

(3)splay时

我们得先找到到根的那条链，然后从上往下把翻转标记下发，然后再进行旋转

Code:

void splay(int now)

{

    int tot=0;

    while(isroot(now)) s[++tot]=now,now=fa;//先拿栈存储链

    s[++tot]=now;

    while(tot) pushdown(s[tot--]);//从上往下下放

    now=s[1];

    for(;isroot(now);Rotate(now))

        if(isroot(fa))

            Rotate(identity(now)^identity(fa)?now:fa);

}

五、洛谷P3690 【模板】Link Cut Tree （动态树）代码参考

Code:

#include <cstdio>

#define ls ch[now][0]

#define rs ch[now][1]

#define fa par[now]

const int N=3e5+10;

int ch[N][2],dat[N],sum[N],tag[N],par[N],s[N],n,m,tmp;

void updata(int now)//正常的更新

{

    sum[now]=sum[ls]^sum[rs]^dat[now];

}

bool isroot(int now)//判断是否为子树的根

{

    return ch[fa][0]==now||ch[fa][1]==now;

}

int identity(int now)//判断是哪个儿子

{

    return ch[fa][1]==now;

}

void connect(int f,int now,int typ)//确定双向父子关系

{

    fa=f;ch[f][typ]=now;

}

void Reverse(int now)//区间翻转，标记管儿子

{

    tmp=ls,ls=rs,rs=tmp,tag[now]^=1;

}

void pushdown(int now)//下发标记

{

    if(tag[now])

    {

        if(ls) Reverse(ls);

        if(rs) Reverse(rs);

        tag[now]^=1;

    }

}

void Rotate(int now)//旋转

{

    int p=fa,typ=identity(now);

    connect(p,ch[now][typ^1],typ);

    if(isroot(p)) connect(par[p],now,identity(p));//注意判断父亲是否为辅助树的根节点

    else fa=par[p];

    connect(now,p,typ^1);

    updata(p),updata(now);

}

void splay(int now)

{

    int tot=0;

    while(isroot(now)) s[++tot]=now,now=fa;//先拿栈存储链

    s[++tot]=now;

    while(tot) pushdown(s[tot--]);//从上往下下放

    now=s[1];

    for(;isroot(now);Rotate(now))

        if(isroot(fa))

            Rotate(identity(now)^identity(fa)?now:fa);

}

void access(int now)//在辅助树中打通一条到原树的链

{

    for(int las=0;now;las=now,now=fa)

        splay(now),rs=las,updata(now);

}

void evert(int now)//将节点提至原树根节点

{

    access(now),splay(now),Reverse(now);//打通，丢上去，翻转

}

void split(int u,int v)//把链抽进辅助树（可以不在一颗辅助树）

{

    evert(u),access(v),splay(v);//放至根，打通，丢上去

}

int findroot(int now)//寻找原树根节点

{

    access(now),splay(now);

    while(ls) now=ls;

    return now;

}

void link(int u,int v)//连边

{

    evert(u);//搞到根

    if(findroot(v)!=u)//保证不在一颗树

        par[u]=v;//只连了虚边

}

void cat(int u,int v)//断边

{

    split(u,v);

    if(ch[v][0]==u)//直接相连

        par[u]=ch[v][0]=0,updata(v);//双向断边注意更新

}

int query(int u,int v)

{

    split(u,v);

    return sum[v];

}

void change(int u,int x)

{

    splay(u),dat[u]=x,updata(u);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d\n",dat+i);

    for(int opt,u,v,i=1;i<=m;i++)

    {

        scanf("%d%d%d",&opt,&u,&v);

        if(opt==0) printf("%d\n",query(u,v));

        else if(opt==1) link(u,v);

        else if(opt==2) cat(u,v);

        else change(u,v);

    }

    return 0;

}

六、特别感谢

FlashHu的博客

高级数据结构【林厚从】

网上许多大神的博客

七、updata

① 事实上，因为\(splay\)会旋转，所以并不一定是真实被连接的边，只是满足了深度关系

我们可以想一想这两种\(cat\)方式的区别

void cat(int u,int v)

{

    evert(u);

    access(v);

    splay(v);

    ch[v][0]=par[u]=0;

}

void cat(int u,int v)

{

    evert(u);

    access(v);

    ch[u][1]=par[v]=0;

}

---

2018.8.11