理解原理后,选择简洁明白的实现方式也是很重要的一环.
十分感谢%%% 陈乐群 的小结,一遍一遍读,发现写得真心不错,要不我还在兜圈子呢.
传送门:https://oi.abcdabcd987.com/summary-of-link-cut-tree/
接下来写一下我自己对模板的理解:
struct splay{
int fa,l,r,siz;//fa:path_parent
bool rev;
}t[N];
其实结构体表示的Splay在写旋转模板时不是那么方便..
既然Splay中的根节点还有父亲，为了确定哪个节点是当前Splay的根，我们必须对正常的Splay tree进行修改。大致有两种方法：
1）在每个节点记下 Root 标记，以确定当前节点是否为它所在的Splay tree的根。然后旋转的时候通过标记下传修改Root标记。
>优点：方便调试
>缺点：LCT的操作写起来麻烦，而且容易出错
2）不记录Root标记，但是修改旋转过程。
>优点：LCT非常好写好理解
>缺点：需要修改splay操作
我个人还是偏向后面那种方法.
另外，LCT操作的实现也有两种方法：
1）固定根，通过修改过的 Access 操作 (Access2) 进行查询和修改。
2）动态根，通过换原树的根和原始的Access进行查询和修改。
很明显第一个由于少了换根，常数肯定要小的多。
但是我觉得第二个理解比较容易，而且比较好写，不容易出错。
void Access(int x)
{
int y=0;
while(x){
Splay(x);
t[x].r=y;
y=x;
x=t[x].fa;
}
}
处理孩子和处理path父节点的方法是类似的，故代码统一：
最初y=0，用来清除x的右子节点，即将边实变虚
之后每次找到path父节点，用y所在的平衡树（之前x已经Splay到根，经过赋值，y为Splay的根）替换x的右子树。（原先x的右子树似乎不作处理？）
直到父节点不存在，即已处理到根。
void MakeRoot(int x)
{
Access(x);
Splay(x);
t[x].rev^=1;
}
评论 (0)
