从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

【热烈庆祝ZOJ回归】

【首先声明:LCT≠动态树,前者是一种数据结构,而后者是一类问题,即:LCT—解决—>动态树】

Link-cut-tree(下文统称LCT)是一种强大的数据结构,不仅可以像树链剖分一样对树上的两点进行询问(权值和、权值的最值……),还可以维护森林的连通性。

学习LCT首推杨哲神犇的《QTREE解法的一些研究》,很详细地解释了LCT的概念及实现

本文则以ZOJ2114一题为例,分析LCT实现过程中的一些事项,并且力求读者对LCT有一个“不次于‘感性’的认识”

叙述过程中会直接引用论文中的术语

题目大意:

N个点(N<=2e4),M次操作(M<=4e4),维护N个点构成的森林

最初N个点两两不连通

U x y z:新建一条权值为z的边,把x所在树的根节点连到y所在的树上

Q x y:询问x到y的距离。如果x和y未连通,输出Not connected.

思路:

对于Q操作,如果x和y所属的根节点不同,那么x和y必然是不连通的

对于U操作,首先需要找到x和y的根节点(分别记作u和v),然后把u连到v上

查询根节点可以用并查集

我们需要对森林进行修改(合并树)及询问操作,树链剖分是无法胜任的(树剖只能用于静态树),所以我们考虑LCT

我们用Splay维护Auxiliary Tree(如果不知道这是什么,请看论文):

 ,Right= };

 struct SplayNode;
 SplayNode* vir;

 struct SplayNode
 {
     int dist;
     int totDist;
     bool isRoot;
     SplayNode* parent;
     SplayNode* child[];
 };

(为阅读方便,分割代码时作了一些修改)

vir的作用是代替空指针,从而免去很多不必要的判断

SplayNode类的成员变量如下:

dist:在森林(原图)中,该节点与父节点之间边的权值。

totDist:Auxiliary Tree中,以该节点为根的子树的dist之和

isRoot:该节点是否为所在Auxiliary Tree的根节点

child[]:该节点在Auxiliary Tree中的左右孩子。

parent:既可以是Auxiliary Tree内部的父节点,也可以是Auxiliary Tree整体的path-parent

(1)如果isRoot==false,那么parent表示该节点在Auxiliary Tree中的父节点

(2)如果isRoot==true,那么parent表示其所在Auxiliary Tree的path-parent

也就是说,对于某个节点u,可能有多个节点以u为parent,但其中只有至多两个与u构成Auxiliary Tree。在编程实现中,这是一个值得注意的问题

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

如图,ABCDE构成森林中的一个连通分量,实线表示Preferred Child

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

相应的Auxiliary Tree(Series)。实线表示Preferred Child关系,虚线表示Path Parent关系

在Auxiliary Tree中,我们“隐式”地把节点的深度作为BST的关键字。也就是说,中序遍历一棵Auxiliary Tree,得到的就是一条从上到下的Preferred Path链

(如果你不能理解从图1到图2的转换,复习一下LCT的相关定义)

之后是Splay的一些操作(成员函数):

     void init()
     {
         dist=totDist=;
         isRoot=true;
         parent=child[]=child[]=vir;
     }

     void update()
     {
         this->totDist =
                 child[Left]->totDist+child[Right]->totDist+this->dist;
     }

     void rotate(int dir)
     //If dir==Right then rotate clockwise, else rotate counter-clockwise
     {
         if(parent==parent->parent->child[Left])
             parent->parent->child[Left]=this;
         else if(parent==parent->parent->child[Right])
             parent->parent->child[Right]=this;

         parent->child[dir^]=this->child[dir];
         child[dir]->parent=this->parent;

         child[dir]=parent;
         parent=parent->parent;
         child[dir]->parent=this;
     }

     void zigzig(int dir)
     {
         parent->rotate(dir);
         this->rotate(dir);

         child[dir]->child[dir]->update();
         child[dir]->update();
         this->update();
     }

     void zigzag(int dir) //dir depends on first rotation
     {
         rotate(dir);
         rotate(dir^);

         child[Left]->update();
         child[Right]->update();
         this->update();
     }

     void zig(int dir)
     {
         rotate(dir);
         child[dir]->update();
         this->update();
     }

     void splay()
     {
         while(!isRoot)
         {
             ;
             ;
             ;

             if(!parent->isRoot)
             {
                 if(parent->parent->isRoot) this->isRoot=true;
                 ;
                 ;
             }
             else
                 this->isRoot=true;

             switch(status)
             {
             : zig(Right);
                     child[Right]->isRoot=false;
                     break;
             : zig(Left);
                     child[Left]->isRoot=false;
                     break;
             : zigzig(Right);
                     if(isRoot) child[Right]->child[Right]->isRoot=false;
                     break;
             : zigzag(Left);
                     if(isRoot) child[Right]->isRoot=false;
                     break;
             : zigzag(Right);
                     if(isRoot) child[Left]->isRoot=false;
                     break;
             :zigzig(Left);
                     if(isRoot) child[Left]->child[Left]->isRoot=false;
                     break;
             default:break;
             }
         }
     }

各函数的说明:

init:初始化。令该节点成为独立的一个连通分量。

update:(在旋转以后)更新节点的totDist值。

rotate:将节点上旋。如果dir==Right,那么沿顺时针方向上旋;如果dir==Left,那么沿逆时针方向上旋。

zig,zigzig,zigzag:Splay的单双旋

splay:提根,将当前节点提到所在Auxiliary Tree的根部

         if(parent==parent->parent->child[Left])
             parent->parent->child[Left]=this;
         else if(parent==parent->parent->child[Right])
             parent->parent->child[Right]=this;

这里的判断需要特别注意。必须写成else if的形式(还记得我们是怎样定义parent的吗?)

另外splay的过程中涉及到isRoot的变化

除此之外其他的部分和普通的SplayTree大同小异,在这里就不多说了,详见代码。

至此,LCT的基础——SplayNode就已经打好了,接下来就是LCT的精华:Access(也有的版本称为Expose)操作:

 int access(SplayNode* u)
 {
     SplayNode* v=vir;
     ;
     while(u!=vir)
     {
         u->splay();
         u->child[Right]->isRoot=true;
         res=u->child[Right]->totDist;
         u->child[Right]=v;
         v->isRoot=false;
         u->update();
         v=u; u=u->parent;
     }
     return res + v->child[Right]->totDist;
 }

 inline int query(SplayNode* u,SplayNode* v)
 {
     access(u);
     return access(v);
 }

比起SplayNode的实现是不是短了许多?(斜眼笑

然而,正所谓浓缩就是精华,Access的原理可以说是不容小视的(毕竟是LCT所有操作的基石)

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

接下来我们以此图(以下称为原图)为例,演示access(H)的全过程。图为access(H)之前

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

access(H)之后的效果图,可以看到途经的所有节点,其原来的Preferred Path都被切断了,取而代之的是“直达”H的Preferred Path

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

access(H)之前的Auxiliary Tree,也是我们操作的对象。

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

首先我们splay(H),把H提到所在Auxiliary Tree的根部

此时H的右子树对应原图中的Preferred Path

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

由于新的Preferred Path要“切断”沿途所有旧的Preferred Child,而H的右子树对应H原来的Preferred Child

所以H和I之间要断开,表示新的Preferred Path到H就中止了,以I为根的子树成为一棵新的Auxiliary Tree

之后别忘了update一下H的totDist

为了将A和H用Preferred Path相连,我们还要对H的Path Parent,也就是对C“开刀”

首先还是splay(C)。当然C已经是Auxiliary Tree的根节点了,所以对于本例,splay(C)什么都没做

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

然后依然将C与右子树D断开。

之后,我们要将C的Auxiliary Tree与H的Auxiliary Tree相连。由于H的Auxiliary Tree在原图中处于C的下方,所以H应该成为C的新的右孩子

如图所示,A和E已经用Preferred Path相连了。至此access(H)过程已经完成。不妨把此时的Auxiliary Tree和上面的效果图对比一下

当然在编程时我们需要一个判断条件:C的parent为vir,再往上走就没有任何意义了,所以access操作停止

……

那么,access的返回值是干嘛的?totDist到底有什么卵用?

举个栗子:询问D到H的距离。我们已经进行了access(H)

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

我们给每条边赋予一个权值(图中用黑色标注)

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

但在LCT的Auxiliary Tree中,这个权值实际上是存储到“下方”的节点中的(图中以红色标注)。括号中是totDist,括号外是dist

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

然后我们access(D)

从ZOJ2114(Transportation Network)到Link-cut-tree(LCT)

这是access(D)之后的Auxiliary Tree

在原图中,D到F的距离可以分解成D到C的距离和C到H的距离。C是D和F的最近公共祖先(LCA)

而在Auxiliary Tree中,这恰好对应C的新、旧右孩子的totDist之和

H是C的”旧“右孩子,被D取代后,D就成了C的”新“右孩子

在编程过程中,我们需要设法保存”旧“右孩子的totDist值(要不然就失联了( ̄▽ ̄")),access函数中的res变量恰好胜任了这一要求

query函数中进行了两次access操作,第一次的返回值因为没有意义所以被丢弃了,而第二次的返回值就是询问的结果

问题已经解决了一半,接下来就是两个子树的合并(并不难):

 ;
 int center[maxN];

 int getCenter(int x)
 {
     return center[x]==x ? x :
            center[x]=getCenter(center[x]);
 }

 inline void link(int u,int v,int len)
 {
     access(node+u);
     node[u].splay();
     center[u]=v;
     node[u].parent=node+v;
     node[u].dist=len;
     node[u].update();
 }

center就是并查集,合并之前,首先要用getCenter函数找到两棵树的根节点u和v,然后把u连到v上

首先access(u),然后splay(u)

splay(u)使u成为所在Auxiliary Tree的根节点,这样在连接u和v时,改变parent指针不会切断u所在的Auxiliary Tree

于是这道题用LCT完美解决(而且效率很高),附上完整代码:

 #include <cstdio>
 #include <cstring>
 #include <algorithm>

 ,Right= };

 struct SplayNode;
 SplayNode* vir;

 struct SplayNode
 {
     int dist;
     int totDist;
     bool isRoot;
     SplayNode* parent;
     SplayNode* child[];

     void init()
     {
         dist=totDist=;
         isRoot=true;
         parent=child[]=child[]=vir;
     }

     void update()
     {
         this->totDist =
                 child[Left]->totDist+child[Right]->totDist+this->dist;
     }

     void rotate(int dir)
     //If dir==Right then rotate clockwise, else rotate counter-clockwise
     {
         if(parent==parent->parent->child[Left])
             parent->parent->child[Left]=this;
         else if(parent==parent->parent->child[Right])
             parent->parent->child[Right]=this;

         parent->child[dir^]=this->child[dir];
         child[dir]->parent=this->parent;

         child[dir]=parent;
         parent=parent->parent;
         child[dir]->parent=this;
     }

     void zigzig(int dir)
     {
         parent->rotate(dir);
         this->rotate(dir);

         child[dir]->child[dir]->update();
         child[dir]->update();
         this->update();
     }

     void zigzag(int dir) //dir depends on first rotation
     {
         rotate(dir);
         rotate(dir^);

         child[Left]->update();
         child[Right]->update();
         this->update();
     }

     void zig(int dir)
     {
         rotate(dir);
         child[dir]->update();
         this->update();
     }

     void splay()
     {
         while(!isRoot)
         {
             ;
             ;
             ;

             if(!parent->isRoot)
             {
                 if(parent->parent->isRoot) this->isRoot=true;
                 ;
                 ;
             }
             else
                 this->isRoot=true;

             switch(status)
             {
             : zig(Right);
                     child[Right]->isRoot=false;
                     break;
             : zig(Left);
                     child[Left]->isRoot=false;
                     break;
             : zigzig(Right);
                     if(isRoot) child[Right]->child[Right]->isRoot=false;
                     break;
             : zigzag(Left);
                     if(isRoot) child[Right]->isRoot=false;
                     break;
             : zigzag(Right);
                     if(isRoot) child[Left]->isRoot=false;
                     break;
             :zigzig(Left);
                     if(isRoot) child[Left]->child[Left]->isRoot=false;
                     break;
             default:break;
             }
         }
     }
 };

 int access(SplayNode* u)
 {
     SplayNode* v=vir;
     ;
     while(u!=vir)
     {
         u->splay();
         u->child[Right]->isRoot=true;
         res=u->child[Right]->totDist;
         u->child[Right]=v;
         v->isRoot=false;
         u->update();
         v=u; u=u->parent;
     }
     return res + v->child[Right]->totDist;
 }

 inline int query(SplayNode* u,SplayNode* v)
 {
     access(u);
     return access(v);
 }

 void initVir()
 {
     vir=new SplayNode;
     vir->init();
 }

 ;

 SplayNode node[maxN];
 int center[maxN];
 int N,Q;
 ;

 inline void link(int u,int v,int len)
 {
     access(node+u);
     node[u].splay();
     center[u]=v;
     node[u].parent=node+v;
     node[u].dist=len;
     node[u].update();
 }

 inline void initNode()
 {
     ;i<=N;i++) node[i].init();
     ;i<=N;i++) center[i]=i;
 }

 int getCenter(int x)
 {
     return center[x]==x ? x :
            center[x]=getCenter(center[x]);
 }

 #define DEBUG
 #undef DEBUG

 #ifdef DEBUG
 ;
 #endif

 void solve()
 {
     lastRes=;
     scanf("%d%d",&N,&Q);
     initNode();
     char cmd;
     int v1,v2,len;
     while(Q--)
     {
         do cmd=getchar(); while(cmd==' ' || cmd=='\n');
         if(cmd=='Q')
         {
             scanf("%d%d",&v1,&v2);
             if(getCenter(v1)==getCenter(v2))
                 printf("%d\n",lastRes=query(node+v1,node+v2));
             else printf("Not connected.\n");
 #ifdef DEBUG
             printf("#%d query successful.\n",++qc);
 #endif
         }
         else
         {
             scanf("%d%d%d",&v1,&v2,&len);
 #ifndef DEBUG
             v1=(v1-lastRes-)%N;
             ) v1+=N;
             v2=(v2-lastRes-)%N;
             ) v2+=N;
 #endif
             link(getCenter(v1),getCenter(v2),len);
         }
     }
 }

 int main()
 {
     initVir();
     int X; scanf("%d",&X);
     while(X--) solve();
     ;
 }

Problem:ZOJ P2114

上一篇:EFcore与动态模型(三)


下一篇:bzoj2631: tree lct