本文将介绍用来解决 动态树问题 的几种数据结构。

参考资料 ： laffey’s blog

LCT

LCT,即Link Cut Tree，是一种用来解决 动态树问题 的数据结构。

LCT可以依靠splay实现，也可以依靠非旋Treap实现，我曾经写了 平衡树学习笔记 来作为这篇文章的前置。

由于依靠splay实现的LCT似乎更好一些，这一部分将主要描述这种LCT。

我们以 P3690 【模板】动态树（Link Cut Tree） 为例，简要阐述这种功能强大的数据结构。

题意简述 ：

给定一颗树，支持修改点权，连边和删边，询问路径异或和。

的精髓在于 虚实链剖分 。其中虚边的链接中认父不认子，实边构成的树会形成一棵 。

基本操作

get 返回当前节点是父节点的左儿子还是右儿子

1
bool get(int x) {return rs(fa[x]) == x;}

isroot 返回当前节点是否是其所在splay的根节点

1
bool isroot(int x) {return ls(fa[x]) != x && rs(fa[x]) != x;}

maintain 利用子节点信息更新父节点信息

本题中维护的信息是子树异或和

1
void maintain(int x){sum[x] = sum[ls(x)] ^ sum[rs(x)] ^ val[x];}

access 打通路径

打通路径指的是 ：

access(x) 操作会将节点 $x$ 到根之间的路径全部变成实边，并且将连向这条路径的其他路径变为虚边。

由于 $splay$ 是按照深度建树，我们可以将 $x$ 旋转到当前 $splay$ 的根节点，于是此时这棵 $splay$ 的右子树就都是原树中深度大于 $x$ 的节点，将右子树分裂出去即可。

然后我们设 $x$ 节点的父亲为节点 $f$ ，我们对 $f$ 进行 $splay$ ，把它的右子树换成节点 $x$ 所在的子树，重复上述过程，我们便完成了 $access$ 操作。

代码实现很简单，就像这样 ： 

1
2
3
4
5
6
7
int access(int x) 
{
    int p;
    for(p = 0;x;p = x,x = fa[x])
        splay(x),rs(x) = p,maintain(x);
    return p;
}

返回值为最后一次虚实链变换时的父节点的编号，即 $x$ 所在 $splay$ 的根，它的父亲一定为空。

makeroot 换根

makeroot 操作可以将指定的点 $x$ 作为原树的根，显然把 $x$ 作为根相当于对这条路径取反，考虑直接维护一个取反标记。

至于为何路径取反是通过交换左右儿子实现 ： 平衡树的中序遍历得到的即为原序列，交换左右儿子的操作就是对于原序列的这一部分进行了左右取反，因此反转了这条路径。

代码如下 ： 

1
2
3
4
5
6
7
8
9
10
11
void make_root(int x)
{
    x = access(x);
    reverse(x);
}

void reverse(int x)
{
    swap(ls(x),rs(x));
    rev[x] ^= 1;
}

findroot

findroot 操作用来找到 $x$ 所在原树的根节点的编号。