~~重新学一次LCT~~

参考论文：SPOJ375 QTREE 解法的一些研究

动态树问题

RT，就是维护一棵或多棵树的路径信息、子树信息，支持对树的分割和合并

Link-Cut Tree是动态树问题一个很好的解决方案

Link-Cut Tree

定义

LCT中使用两种边来连接同一棵树中的节点：\(\text{Preferred Edge}\)和\(\text{Parent Edge}\)

类似于重链剖分中的轻边和重边，每个非叶子节点恰好有一条\(\text{Preferred Edge}\)指向儿子节点

由\(\text{Preferred Edge}\)组成的路径称为\(\text{Preferred Path}\)

\(\text{Preferred Path}\)的顶端节点由\(\text{Parent Edge}\)与其父节点相连

\(\text{Preferred Path}\)由\(\text{Access}\)操作产生

\(\text{Access(x)}\)操作将根节点到x的路径变为\(\text{Preferred Path}\)，原来指向这条路径的所有\(\text{Preferred Edge}\)变为\(\text{Parent Edge}\)

这样，一棵树就被划分成若干条\(\text{Preferred Path}\)，并由\(\text{Parent Edge}\)相连

因为\(\text{Splay}\)可以非常方便地实现分裂和合并，我们可以用\(\text{Splay}\)维护每一条\(\text{Preferred Path}\)的信息

\(\text{Splay}\)左子树中的节点代表\(\text{Preferred Path}\)中更上面的节点，\(\text{Splay}\)右子树中的节点代表\(\text{Preferred Path}\)中更下面的节点

操作

Access

\(\text{Access(x)}\)操作的意义在于将x到根的路径变为同一棵\(\text{Splay}\)，方便其他操作

实现十分暴力：一路向上修改每棵\(\text{Splay}\)的信息。可以证明，\(\text{Access}\)操作的复杂度是均摊\(O(logn)\)的

1	inline void access(int x) {for (int t=0;x;t=x,x=fa[x]) splay(x),s[x][1]=t,pushup(x);}

不要忘了更新\(\text{Splay}\)信息

MakeRoot

LCT经常需要用到\(\text{MakeRoot}\)操作，将某个点变成整棵树的根，这对一些关于树形态的操作很有用

实现：

\(\text{Access(x)}\)，此时x在\(\text{Preferred Path}\)的底端
\(\text{Splay(x)}\)，此时x变为\(\text{Splay}\)的根，但所有节点都在左子树（\(\text{Preferred Path}\)的上端）
\(\text{Flip(x)}\)，将整棵\(\text{Splay}\)翻转，x就变成了\(\text{Preferred Path}\)顶端

1	inline void mr(int x) {access(x),splay(x),addflip(x);}

Join

\(\text{Join(x,y)}\)的作用是将x变为y的一个儿子

直接把x变成根节点，再连一条\(\text{Parent Edge}\)就好了

1	inline void join(int x,int y) {mr(x);fa[x]=y;}

Cut

\(\text{Cut(x,y)}\)的作用是删除边\((x,y)\)

实现：

\(\text{MakeRoot(x)}\)，\(\text{Access(y)}\)，这样根节点所在\(\text{Splay}\)只有x,y两个点了
\(\text{Splay(y)}\)，此时\(\text{Splay}\)中x一定是y的左儿子，fa[x]=son[y][0]=0即可

1	inline void cut(int x,int y) {mr(x),access(y),splay(y);if (s[y][0]==x) fa[x]=s[y][0]=0;}

GetRoot

\(\text{GetRoot(x)}\)获取x所在树的根

先\(\text{Access(x)}\)，此时x所在\(\text{Splay}\)的最左节点就是根了

暴力往左走即可，因为\(\text{Splay}\)的深度是均摊\(O(logn)\)的

注意点：

一定要记得一路\(\text{Pushdown}\)
最后再\(\text{Splay}\)根节点，不然复杂度是错的

1	inline int getrt(int x) {access(x),splay(x);while (s[x][0]) pushdown(x),x=s[x][0];splay(x);return x;}

其他

获取x到y路径的信息：
- 先\(\text{MakeRoot(x)}\)，\(\text{Access(y)}\)，把这条路径放在一棵\(\text{Splay}\)里
- 注意到此时x不一定是Splay的根了，还要\(\text{Splay(y)}\)一下，才能获得整个路径的信息
获取LCA(x,y)：
- \(\text{Access(x)}，\text{Access(y)}，\text{Splay(x)}\)
- 此时fa[x]就是LCA了
- 特判：x没有fa时，LCA是x

复杂度分析

不难发现，LCT的时间复杂度基于\(\text{Access}\)操作，所以总时间复杂度为\(O(nlogn)\)

关于\(\text{Access}\)操作的复杂度证明，详见论文

空间复杂度为\(O(n)\)

模板

int s[maxn][2],fa[maxn];
bool flp[maxn];
#define isroot(x) (s[fa[x]][0]!=x&&s[fa[x]][1]!=x)
inline void addflip(int x) {swap(s[x][0],s[x][1]);flp[x]^=1;}
inline void pushup(int x) {/* do something */}
inline void pushdown(int x) {if (flp[x]) flp[x]^=1,addflip(s[x][0]),addflip(s[x][1]);}
inline void rotate(int x){
    int f=fa[x],g=fa[f],d=s[f][0]==x;
    if (!isroot(f)) s[g][s[g][1]==f]=x; fa[x]=g;
    s[f][d^1]=s[x][d]; fa[s[x][d]]=f; pushup(f);
    s[x][d]=f; fa[f]=x; pushup(x);
}
int top,stk[maxn];
inline void splay(int x){
    stk[top=1]=x;
    for (int i=x;!isroot(i);i=fa[i]) stk[++top]=fa[i];
    while (top) pushdown(stk[top--]);
    while (!isroot(x)){
        int f=fa[x],g=fa[f],d=s[f][0]==x,dd=s[g][0]==f;
        if (!isroot(f))
         if (d==dd) rotate(f),rotate(x);else
          rotate(x),rotate(x);
        else rotate(x);
    }
}
inline void access(int x) {for (int t=0;x;t=x,x=fa[x]) splay(x),s[x][1]=t,pushup(x);}
inline void mr(int x) {access(x),splay(x),addflip(x);}
inline void join(int x,int y) {mr(x);fa[x]=y;}
inline void cut(int x,int y) {mr(x),access(y),splay(y);if (s[y][0]==x) fa[x]=s[y][0]=0;}
inline int getrt(int x) {access(x),splay(x);while (s[x][0]) pushdown(x),x=s[x][0];splay(x);return x;}  //!!!
//...
if (getrt(x)!=getrt(y)) join(x,y); //加边 
cut(x,y); //删边
mr(x);access(x); //修改x的点权
mr(x);access(y);splay(x); //获取(x,y)路径的信息

linkfqy

A link to the past.

Link-Cut Tree 学习笔记