一棵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上的实际操作。
实际操作中,我们要断掉\(p\)下面的点,并将\(p\)所在链连接到它上面的一个点\(t\)上,然后断掉\(t\)下面的点。大概是这样:
每经过一次这样的操作,\(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)\)这条链的辅助树,然后就可以为所欲为啦。