Link/cut Tree

时间:2021-12-23 11:30:02

一棵link/cut tree是一种用以表示一个森林,一个有根树集合的数据结构。它提供以下操作:

  • 向森林中加入一棵只有一个点的树。
  • 将一个点及其子树从其所在的树上断开。
  • 将一个点连接至另一个顶点,作为其子节点。
  • 求出一个点所在树的根。通过对两个不同的点进行此操作,我们可以判断他们是否属于同一棵树。

    翻译自Link/cut tree - Wikipedia,英语好的小伙伴看这个就很不错

在link/cut tree中,边分为两种:偏爱边(preferred edges)和普通边(normal edges),每个非叶节点都有一条偏爱边指向其偏爱子节点(preferred child)。偏爱边形成的路径称为偏爱路径(preferred paths)

实际上,link/cut tree是将森林划分为若干条链(也就是偏爱路径),并用以深度作为splay去分别维护每一条链。这些splay被称为辅助树(auxiliary tree)。操作时不要考虑splay的结构,只要考虑原树的结构就好。

link/cut tree主要支持四种操作makeRt(p)cut(p)link(p,q)path(p,q),而这些操作都是基于access(p)的。下面分别介绍如何实现这些操作。

Access

void access(int p) {for(int q=0;p;q=p,p=fa[p]) splay(p),ch[p][1]=q,update(p);}

首先当然要介绍作为万恶之源的access(p)access(p)的效果是将\(p\)与其所在树的根置于一条链上,并且\(p\)是这条链的末尾。可以看一下wiki的这张图:

左边是access(l)前,中间是access(l)后,右边是在splay上的实际操作。

Link/cut Tree

实际操作中,我们要断掉\(p\)下面的点,并将\(p\)所在链连接到它上面的一个点\(t\)上,然后断掉\(t\)下面的点。大概是这样:

Link/cut Tree

每经过一次这样的操作,\(p\)就会连接到上一层的链上。反复操作直到\(p\)与\(rt\)相连。

在辅助树中,断掉\(p\)下面的点相当于splay(p)并改变ch[p][1]。\(q\)记录应该将谁接在\(t\)下面,也就是上一次的\(p\)啦。

MakeRt

void makeRt(int p) {access(p); splay(p),rever(p);}

rever(p)表示翻转splay中的\(p\)。当我们access(p)后,\(p\)成为了其所在链上最深的点,那么splay(p)后\(p\)就只有左子树。翻转\(p\)就把\(p\)变成了链上最浅的点,也就是根啦。

这段细节上我也想不太明白...别的点怎么啦?每条链都没有变化(只是存储链的splay结构变化了),链之间的连接也没有变化,那么原树的结构就不会变化。

Cut

void cut(int p) {access(p); splay(p),fa[ch[p][0]]=0,ch[p][0]=0; update(p);}

断掉\(p\)上面的点,也就是断掉与ch[p][0]的连接。

Link

void link(int p,int q) {makeRt(p); fa[p]=q;}

如果\(p\)是一棵树的根的话,直接将\(p\)接在\(q\)下面就可以了。

Path

void path(int p,int q) {makeRt(p),access(q),splay(q);}

将\(p\)变为根,再把\(q\)和根(也就是\(p\))置于同一链上。这样就形成了一个只维护\((p,q)\)这条链的辅助树,然后就可以为所欲为啦。