动态树的相关概念
动态树: 动态树就是动态的维护一个森林,能够动态的添加或删除一些边,同时维护树上的一些信息。
动态树的原理:
动态树中的边分为虚边和实边,每个节点最多只会有一条实边连出去,也可以没有实边。用实边连成的路径称为实边路径,没有实边的孤立点也被看作一条实边路径。动态树就是通过维护实边之间的关系来维护整棵树。
在树链剖分中,我们使用线段树或树状数组来维护重链。而在动态树中,由于要支持添加和修改操作,因此这里要使用一些更加灵活的数据结构去进行维护,这里会用 $Splay$ 来维护所有的极大的实边路径。而 $Splay$ 是用类似于维护区间的方式来维护实边路径的,整个 $Splay$ 的中序遍历就是一条从上到下的实边路径。
在所有实边路径之间,存在很多虚边,如果某个节点和它的父节点不在同一个实边路径中,则它们之间的边就是虚边。
由于一个 $Splay$ 的中序遍历是一条从上到下的实边路径,因此对于 $Splay$ 中的某一个点,它在树中的子节点应该是在 $Splay$ 中的后继节点,它在树中的父节点应该是在 $Splay$ 中的前驱节点。
注意,这里使用 $Splay$ 中的前驱后继关系来维护树中的父子关系,$Splay$ 中的父子关系只是用来维护中序遍历的,和树中的父子关系是毫无关联的。
而对于所有的虚边,可以发现任何一条虚边都是某一条实边路径中的最上面的一个点和它在树中的父节点之间的边。可以发现在每个 $Splay$ 中,它的根节点的父节点是没有被用过的,因此我们可以用每个 $Splay$ 的根节点来维护它所对应的实边路径最上面的节点和其父节点之间的虚边。
到此,我们就能用每个 $Splay$ 去维护每条实边路径,然后用每个 $Splay$ 的根节点去维护实边路径之间的虚边,这样就能用 $Splay$ 维护区间的方式来维护好整棵树。
对于发现,对于每条实边,父节点是连向子节点的,子节点也是连向父节点的,但是对于每条虚边,只有子节点连向父节点,父节点并没有连向子节点,因此对于每条边,我们可以通过父节点是否指向子节点来判断这条边是实边还是虚边。而这样的好处就是对于任意一个节点,我们可以任意选择这个节点所对应的实边,如果我们想将当前这条实边 $(u, v)$ 换成另一条边 $(u, x)$ 的话,只需要让这个节点的后继 $v$ 更换成 $x$ 即可。可以发现,这样我们就能非常容易的将一条实边删掉换成另一条虚边。
动态树能实现的操作:
$access(x)$: 将根节点到 $x$ 的路径变成实边(建立一条从根节点到 $x$ 且只能到 $x$ 的实边路径)。
我们需要将根节点到 $x$ 的路径上的边都变成实边,然后将冲突的边变成虚边,可以从小到大来操作。
首先我们先要从 $x$ 往上找到一条虚边,由于虚边都存储在 $Splay$ 中根节点的位置,所以我们需要先将 $x$ 在 $Splay$ 中转到根节点,此时 $x$ 和 $x$ 的父节点 $p$ 的关系就会对应这条虚边,此时我们要想将 $(x, p)$ 这条边变成实边,就要将 $x$ 变成 $p$ 的后继,所以我们需要先将 $p$ 转到根节点,由于 $p$ 此时应该是它所在的实边路径中最下面的一个点的,因此 $p$ 被转到根节点之后,它的右子树就应该是空的,那么我们就只需要将以 $x$ 为根的这个 $splay$ 插入到 $p$ 的右子树中就行了。此时我们就将两条实边路径中间的虚边变成了实边,合并成了一条实边路径,且它对应的是一个以 $p$ 为根节点的 $Splay$,此时 $p$ 和它父节点之间的边又对应了更上面的一条实边,我们继续用刚才的方法将两个实边路径合并。直到合并后的 $Splay$ 的根节点没有父节点为止,说明已经将整个路径都合并成实边了。
在合并过程中,可能 $x$ 的父节点此时已经存在一条实边,但是我们并不需要再进行额外的处理,因为更换实边本身就是一个更换后继的过程,而我们在合并的时候就是将整个右子树进行了更换,此时不管它原本时候存在后继,都已经被我们更换成了新的后继,此时原本的实边自然就被更换成了新的实边。
$make\_root(x)$: 将 $x$ 变成整棵树的根节点。
这个操作就比较简单了,我们可以先用 $access(x)$ 建立一条从根节点到 $x$ 的实边路径,首先这整棵树其实是一棵无向树,每条边都是无向的,而对于一条无向路径来说,我们将整个路径翻转一下并不会影响整棵树的拓扑结构。由于 $Splay$ 的中序遍历表示的是从上到下的实边路径,所以此时的中序遍历应该是从根节点到 $x$ ,因此我们可以将 $x$ 转到根节点,然后将整个路径翻转过来。翻转之后中序遍历就变成了 $x$ 到根节点,转化会实边路径后 $x$ 就变成了最上面的一个点,也就是整棵树的根节点。
$find\_root(x)$: 找到 $x$ 所在的实边路径的根节点。
对于 $x$ 所在的实边路径的根节点应该是它对应的 $Splay$ 的中序遍历的最左边的节点,因此我们首先还是用 $access(x)$ 建立一条从根节点到 $x$ 的实边路径,然后将 $x$ 旋转到所在 $Splay$ 的根节点,此时 $x$ 所在实边路径的根节点就是 $x$ 的左子树中的最左边的一个节点,因此我们从 $x$ 一直往左搜到底就是我们要找的点。
而该操作也可以用来判断两个点是否在同一条实边路径中。
$split(x, y)$: 将 $x$ 到 $y$ 的路径变成一条实边路径。
结合前面的操作就能轻易的实现这一操作,我们通过 $make\_root(x)$ 将 $x$ 变成整棵树的根节点,然后就能通过 $access(y)$ 建立一条从 $x$ 到 $y$ 的实边路径
$link(x, y)$: 若 $x, y$ 不连通,则加入 $(x, y)$ 这条边。
我们可以先通过 $make\_root(x)$ 将 $x$ 变成整棵树的根节点,然后用 $find\_root(y)$ 找一下 $y$ 所在的实边路径的根节点,如果 $x, y$ 连通,则 $y$ 所在的实边路径的根节点就是 $x$,否则说明不连通,那么就从 $x$ 向 $y$ 连接一条边 $(x, y)$,而 $make\_root(x)$ 不仅会将 $x$ 变成整棵树的根节点,同时还会将 $x$ 变成所在 $Splay$ 的根节点,此时其实就是从 $x$ 所在的 $Splay$ 向 $y$ 连一条虚边,本质上就是将 $x$ 的父节点变成 $y$ 即可。
$cut(x, y)$: 若 $x, y$ 之间有边,则删掉该边。
我们先通过 $make\_root(x)$ 将 $x$ 变成整棵树的根节点,然后通过 $find\_root(y)$ 判断一下 $y$ 所在实边路径的根节点是不是 $x$,若是,说明 $x, y$ 在同一条实边路径中,而 $find\_root(y)$ 在查找 $y$ 所在实边路径的根节点的同时,还会将 $y$ 所在实边路径的根节点变成整棵树的根节点,因此 $y$ 所在实边路径的根节点就应该是 $x$,如果 $x, y$ 之间有边,那就意味着 $y$ 是 $x$ 的后继,因此我们只需要判断一下 $y$ 是不是 $x$ 的后继,就能知道 $x, y$ 之间是否有边,若有边,将其删去即可,而只要 $y$ 是 $x$ 的右子节点且 $y$ 不存在左子树,就意味着 $y$ 是 $x$ 的后继
$is\_root(x)$: 判断 $x$ 是不是所在 $Splay$ 的根节点。
判断方法很简单,只需要判断一下 $x$ 是不是它的父节点的左儿子或右儿子,若都不是,说明 $x$ 和它的父节点之间的边是一条虚边,此时 $x$ 必然是根节点。
以上就是 $Link\_Cut\_Tree$ 版本的动态树所能实现的全部操作,至于如何维护树中每个节点的信息,只需要将信息放入 $Splay$ 里面进行维护即可。另外由于动态树本身需要实现翻转操作,因此 $Splay$ 本身需要一个 $rev$ 懒标记来记录子节点是否需要翻转。而由于本题中每个 $Splay$ 记录的树都是一条链,所以可以直接用一维的 $Splay$ 来维护即可。
注意!对于懒标记通常是我们从上往下递归的时候顺便往下传的,但是在动态树中存在从下往上的操作,比如我们要进行 $Splay$ 将 $x$ 转上去时,但是上面的懒标记还没有传下来,这就会导致结果出错,为了能将懒标记正确的从上往下传下来,我们就需要先从 $x$ 遍历到根节点,然后再从上往下去将所有懒标记传下来,而这里就要用到一个栈来做辅助。