动态树的具体操作

-------------------(摘自《高级数据结构》)

用splay维护实路径，
用深度作为关键字给节点排序，那么我们将得到唯一一个有序节点。
在实现操作之前，我们还需要维护一些额外信息。为了能够在这些实路径之间建立关系，使得我们能够知道这些路径在树结构中的组织方式，我们要为每一颗splay树额外维护其path-parent，即每颗splay对应的实路径中深度最小的父节点。注意实路径，splay以及维护的森林这三者之间的关系和区别。
access(v)
上述操作中除了第一个意外，其余都需要用到基础操作，access（v）,
1)如果节点v不是其所在实路径头部，即v有子节点u与之用实边相连，那么需要先断开这条边，方法是首先将节点v用splay操作旋转到哦其所在平衡树的根节点，然后v肯定有右子树，故将v与v的右子树分离，同时将v的右子树的path-parent设置为v；
2)如果节点v所在的平衡树包含根节点，那么该过程结束；否则，转步骤3）
3）设u为v所在的平衡树的path-parent。将u用splay操作旋转到其根节点，并且用v所在的平衡树替换u的右子树，这样就实现了路径的向上延伸。还需要分离原来u的右子树，原来的右孩子记为w。此时w的path-parent就为u了。然后继续转步骤2）

void access(v){
splay(v);
v->rightchild->Path_Parent=v;
v->rightchild=Null;
while (v->Path_Parent!=Null){
  u=v->Path_Parent;
  splay(u);
  u->rightchild->Path_Parent=u;
  u->rightchild=v;
 v=u;
 }

return 0;
}
//这段伪代码很好理解

2.find_root(v)
有了access(v)操作，寻找树根的操作就比较简单了。我们只要对节点v执行access（v）操作，使得v与要找的根节点在同一颗平衡树中了。然后，要找的根节点一定是实路径的尾部，即平衡树中的最左节点。

void find_root(int v){
   access(v);
   splay(v);//此处还没想通为啥要splay一次。
   while（v->leftchild!=Null）
   {
     v=v->leftchild;
  }
return v;
}

3.evert(v)
该操作等价于将v到v所在的树的根节点的路径上的所有边取反。首先执行acess(v)，我们便已经将该条路径取出了。由于路径是用平衡树维护的，所以需要执行的是平衡树的逆序。普通方法重构平衡树需要O（n）的时间，然而实际上我们可以借鉴线段树的延迟修改思想，给平衡树节点也打上标记进行反序。这里由于是对整颗平衡树反序，所以标记应该打在平衡树的根节点处，用打标记的方式维护的时候，要对平衡树的旋转等操作进行相应的维护。

void evert(int v)
{
  access(v);
  splay(v);
  reverse(v);
}

4.link(u，v）
为了保证连接后得到的树的形态仍然合法（即为有根树）我们首先需要令u成为其所在树的根节点。我们将u变为其所在树的根节点，同时要将u用splay操作移动到平衡树的根节点。此时，u的左子树必然为空。我们将v用splay操作移动到其所在平衡树的根节点。然后令u的左孩子为v，完成连接操作，然后令u的左孩子为v，便完成了连接操作。

void link(int u,int v){
evert(u);
access(u);
splay(u);
access(v);
splay(v);
u->leftchild=v;
}

5.cut(u,v)
执行该操作时，首先要将u置为有根树的根节点，从而保证v一定是u的子节点，再对v执行access操作，我们便将u和v合并到同一颗平衡树中了。此时对v执行splay操作使其成为所在平衡树的根节点，同时分离v和v的左子树，便完成了删边操作。

void cut(int u,int v)
{
evert(u);
access(v);
splay(v);

v->leftchild=Null;
}

Make_Tree操作和其他一些操作略去。