前面所提到与树有关的数据结构，大部分都是在一棵树上进行的。如果是在森林中连边和删边，就要使用 LCT 了。LCT 可以看作是树链剖分与 Splay 树的组合，建模中用到了树链剖分，但实际写起来与树链剖分没什么关系，主要用 Splay 树。它的平摊时间复杂度为 \(\mathcal{O}(\log N)\)。
1 LCT 的思想
-
把树分为多条链。在一条链中，边用实链存储（儿子指向父亲，父亲指向儿子），在不同的链中，边用虚边存储（儿子指向父亲，父亲不指向儿子）。这样在一条链中，只维护了这条链的信息（由于父亲不指向儿子，在
push_up时不会更新儿子的信息，也就只维护了这条链的信息）。在实际操作中，如果要对一条链（两点之间的路径）进行操作，则只需要将这条链分裂出来即可。 -
将原树转换为辅助树。这个转换非常精妙。将原树中的实链与虚边提取出来，形成一个新的辅助树。这棵树看起来与原树差别很大，但从其中可以还原出原树的路径特征。因此我们只需要处理辅助树即可。
-
实链与 Splay 树。实链是动态变化的，使用 Splay 处理实链，主要是因为 Splay 有“提根”与改善树的形态功能。
下面介绍 LCT 的建模步骤与操作。LCT 的概念很多，操作比较复杂，读者可以多看几遍，加深理解。
2 从原树到辅助树
- 将原树剖分为实链和虚边
和树链剖分差不多，每个结点只能向它的儿子中连一条实链。所有非实链的边都是虚边。LCT 对实链和虚边的选择没有要求，整棵树全为虚边也是没问题的。下面是一种剖分的方法。
原树：
剖分后：
- 将原树转换为辅助树
首先是实链的转换。每条实链都是一条路径，深度递增。将每个点的深度看作权值，建一棵 Splay 树。在这棵树上进行中序遍历，便能得到原来的链。
下面是一种可以的转换方法。
原树上将同一条链上的结点圈起来：
将链转换为 Splay 树：
每棵 Splay 树旋转并不会改变中序遍历，也就不会改变链的形态，从而保持了原树的特征。
可以发现，在上图中，原来 \(3 \to 1\) 的虚边转化成了 \(6 \to 1\) 的虚边。这样会影响 LCT 的形态吗？答案是不会。在原树中，连接虚边的是一条链的链头，比如上图中，\(3-6-9\) 这条链的链头 \(3\) 有一条虚边。在辅助树中，如果一个点连接了虚边，则代表这个点所在的 Splay 树中，深度最低的点连接了虚边。如上图，\(6 \to 1\) 这条虚边实际上是 \(6\) 所在的 \(Splay\) 中深度最低的点 \(3\) 连接的。
这样一棵辅助树就建成了。
3 LCT 的操作
我们已经得到了辅助树了，那应该如何实现连边和断边操作呢？
下面介绍 LCT 的基本操作。在阅读时，要注意区分是在连通块中操作，还是在一条链中操作；是在原树中操作，还是在辅助树中操作。
1 splay() 与 access()
在这些操作中，最根本的操作是 splay() 和 access()。splay(u) 的功能是将 \(u\) 旋转到这条链（不是连通块）的最顶端。access(u) 的功能是将 \(u\) 与该连通块中深度最低的点连一条实链。下面讲解一下 access() 的实现过程。
如果在上图中执行 access(7)，则执行的过程如下：
- 初始的辅助树：
splay(7)，得到：
- 将实链 \(7-10\) 改为虚边，使 \(7\) 成为实链中最底端的点：
-
splay(6)。\(6\) 已经是该链深度最小的点，树不变。 -
将实链 \(6-9\) 改为虚边，将 \(6\) 的右儿子改为 \(7\) 并连实链：
splay(1)，得到：
- 将实链 \(1-2\) 改为虚边，将 \(1\) 的右儿子改为 \(6\) 并连实链：
这样 \(1,3,6,7\) 形成了一棵 Splay 树，中序遍历得到 \(1,3,6,7\)，这正是在原树中的顺序。可以看出，LCT 可以随意改变实链与虚边，十分灵活。
access() 函数是由 splay() 函数实现的，时间复杂度为 \(\mathcal{O}(\log N)\)。
2 make_root()
该函数的作用是将 \(u\) 旋转到原树中的根。上面的操作都在辅助树中进行，该函数可以改变原树的形态，是 LCT 的重要技巧。
在原树中，如果要查询 \(2-1-3\) 这条路径，会发现这条路径中结点的深度不是递增的，无法在辅助树中处理这条链。但如果把 \(2\) 旋转到根节点，那么路径就是递增的了。
旋转前：
旋转后：
该函数分为 \(3\) 步：
access(u) \(\to\) splay(u) \(\to\) tag(u)，其中 tag(u) 表示打区间翻转的标记。
access(u) \(\to\) splay(u) 执行完后，\(u\) 变为辅助树中的根节点，且为它与原来根节点所连接的实链中，深度最大的点。此时我们执行区间翻转，则 \(u\) 就变成了实链中深度最小的点。