Link-Cut Tree

考古时间：

谁发明的？ Sleator和Tarjan
什么时候？ 1983年

Tarjan，永远的神。

常用于解决动态树问题的数据结构。

从问题引入

维护一个森林，支持如下操作
加边/删边，操作后仍是一个森林。
询问两点连通性，修改/查询链信息。（暂不考虑子树信息）

回顾树链剖分的过程：

1. 依据子树大小将树边分为轻边和重边
2. 用数据结构维护重链信息（线段树）

核心是链的剖分与维护的过程。

尝试延拓这个做法用于解决动态树问题：

由静态到动态——启示我们用更“动态化”的数据结构维护链信息。

这里，最通常的选择是splay。

链的剖分仍然存在，不过由于结构变化的任意性，按照固定的规则进行剖分可能会变得很复杂。我们希望能够实现自定义（任意的）链剖分。

也就是说，我们想要实现这样一个结构：

对于一棵树，有轻边/重边的剖分，其中重链用一棵splay维护。
支持将任意的路径转化为重链，从而将这条链上的信息整合入同一棵splay内，便于统计。

定义

辅助树（auxiliary tree）：在 LCT 中，用于维护重链信息的 Splay。其维护的键值 key 为节点在原树中的深度。

性质1：其中序遍历（左中右）即这条链从根到叶子方向的顺序。

性质2：辅助树是一棵树，辅助树是一棵 Splay，原树每个节点与辅助树的 Splay 节点一一对应。

性质3：每一颗辅助树不是孤立的，因为我们还需要维护原树的形态信息。每颗 Splay 的根节点的 fa 指针指向这条链的顶端节点在原树中的父亲。（实际上，这个指针一一对应原树中的虚边，需要注意的是，这个指针是由下向上单向的）

可以发现，原树中的所有信息都被一一对应到了所有辅助树中，我们可以随时由辅助树森林还原出原树，所以接下来的讨论我们只需要考虑操作对辅助森林结构的影响。

访问（access）：从树根出发，将根到某个节点的路径设置为重链。（提取信息的过程）

重儿子（偏好儿子，preferred child）：访问到的树链的最底层节点。
重边（偏好边，preferred edge）：重链中，指向重儿子方向的边。
重链（偏好链，preferred path）：访问时走过的路径，由重边和重儿子组成。

如上是一个例子。

现在考虑如何应用这个结构解决问题，同时维护这个结构：

这个过程和我们对非旋treap的构建很类似，通过组建核心函数并且调用来实现各种操作。

先考虑我们手里有什么：

Splay(x) —— 将 x 置为其所在 Splay 的根
Pushup(x) —— 用 x 儿子的信息更新 x 的信息
Pushdown(x) —— 用 x 的 lazy 信息更新 x 的儿子们的信息

首先，我们实现最核心的函数，access(x)

其功能是，从树根出发，将根到某个节点的路径设置为重链。

void access(int x)
{
    int tmp=0;
    while(x)
    {
        splay(x);
        ch[x][1]=tmp;
        pushup(x);
        tmp=x,x=fa[x];
    }
}

就这？
就这。

分析一下为什么就work了，从x自底向上的进行，每次把x设为所在辅助树（重链）的根，此时右儿子的子树里面的节点是这条链不需要的一部分，切掉。将上一棵 splay 连上去就行了。

发现一个问题，我们刚刚描述的树链都是自底向上的链，而实际问题我们会遇到深度不单调的链。所以现在需要这样一个函数：makeroot(x)

其功能为，将一个点设为目前树的根。

void makeroot(int x)
{
    access(x);
    splay(x);
    rev[x]^=1;
}

考虑刚刚的结构中只通过 Splay 的结构表示了原树的深度信息，所以翻转操作可以实现换根。

这样对于一个任意的链操作，只要把一个点设为根节点，然后查询另一个节点到根的链信息即可。

所以下面几个函数的构建就是水到渠成的了：

void split(int x,int y)
{
    makeroot(x);
    access(y),splay(y);
}

分离一条路径，此时这条路径就是y和y的左子树。（深度小于等于y）

void link(int x,int y)
{
    makeroot(x);
    fa[x]=y;
}
void cut(int x,int y)
{
    split(x,y);
    if(ch[y][0]==x)ch[y][0]=fa[x]=0;
}

一些需要注意的点：

如何判断一个点是一棵 Splay 的根？