LCT（动态树）（洛谷P3690）（BZOJ3282）

推荐这篇论文

前置技能

Splay和树链剖分

简介

动态树问题, 简称LCT，近几年在OI中兴起的一种新型问题，是一类要求维护一个有根树森林，支持对树的分割, 合并等操作的问题。

算法用途

比如维护一个数据结构，有如下操作：

1.查询路径权值和。

2.查询LCA。

3.修改单个点的权值。

4.断开两个点，使之成为两棵树。

5.合并两个点，使之成为一颗树。

当然还可以有关于子树的操作，但是这个需要用到另一种数据结构叫TopTree。这里暂时只讲LCT。

算法实现

几个定义

Preferred Child：在v的子树中，如果最后被访问的节点在子树w中，则称w是v的Preferred Child。特殊的，如果最后被访问的节点就是v本身，则v没有Preferred Child。

Preferred Edge：连接v与其Preferred Child的边。

Preferred Path：由Preferred Edge构成的不可再延伸的路径。

Path Parent：Preferred Path中最高点的父亲节点。特殊的，如果这条Preferred Path的最高点就是根节点，则这条Path没有Path Parent。

因为操作需要支持分离与合并，因此我们用Splay来维护每一条Preferred Path。

各种操作

Access(x)

所谓access(x)，即访问x节点。当x被访问后，x到根节点的路径就变成了Preferred Path。

给张图体会一下：

Access的实现非常暴力。假设当前节点为x，上一个节点为v（即x是v所在Preferred Path 的 Path Parent）。每次直接把x的Preferred Child。但是由于有Splay，我们就先把x Splay到根。如果x有右子树（即x的Preferred Child），那么就把x与它的右子树断开，接上v。x原来的右子树就重新建一颗树，其Path Parent为它自己。一直做到Preferred Path包含根节点为止。

MakeRoot(x)

让x成为树的根。

先Access(x)，此时x与根节点就在同一颗平衡树上了。接着把x Splay到根，因为x必然是最深的点，所以Splay后所有的节点都在x的左边。此时只要交换x的左右子树，就可以把x变成树的根了。而这个操作可以同区间翻转一样打个Tag来实现。

Cut(x,y)

断开x和y。

先MakeRoot(x)，再Access(y)，此时x和y就在同一颗平衡树上了，且这棵树上只有x和y，根节点为y。再把y的左子树(x)和x的父亲(y)清零。

Link(x,y)

MakeRoot(x)，再把x的父亲记为y即可。

代码

iv access(int x){ for (int i=;x;i=x,x=t[x].fa) splay(x),t[x].to[]=i,pshp(x); }
iv makeroot(int x){ ccss(x),splay(x),t[x].f^=; }
iv link(int x,int y){ mkrt(x),t[x].fa=y; }
iv cut(int x,int y){ mkrt(x),ccss(y),splay(y); if (t[y].to[]==x) t[y].to[]=t[x].fa=; }
           

（扩展）LCA(x,y)

先后访问x和y，再Splay(y)。此时LCA(x,y)即为x的Path Parent。

复杂度证明

博主太菜不会证明就引用了

Splay的总效率为O((n+Q)∗log2(n))，但是Access的总效率呢？

Access的效率取决于Prefered Child改变的次数，而Prefered Child改变的次数取决于Prefered Edge改变的次数。Prefered Edge和普通边不禁让我们想到了轻重链剖分中的重边和轻边。根据轻重链剖分的定义，我们会发现每次Access，至多有log2(n)条普通边变成了轻的Prefered Edge，也就是说普通边变成轻的Prefered Edge的总次数为(n+Q)∗log2(n)。但是有多少普通边变成了重的Prefered Edge呢？我们转化一下，普通边变成重的Prefered Edge的次数=重的Prefered Edge变成普通边的次数+n（可能最后全是重的Prefered Edge），而重的Prefered Edge变成普通边必定意味着一条普通边变成了轻的Prefered Edge，所以普通边变成重的Prefered Edge的次数=(n+Q)∗log2(n)+n。

综上所述Access的总效率为O((n+Q)∗log2(n))，也就是说LCT的总效率为O((n+Q)∗log2(n))。

ps：然而Splay常数巨大，所以LCT常数巨大……

模板

以洛谷P3690（BZOJ3282）为例：

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 300005
#define il inline
#define iv il void
using namespace std; 
struct node{
    int to[],fa,f,p;
}t[N];
int n,m,a[N],stk[N],tp;
il char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    if (l==r) return EOF; return *l++;
}
il int _read(){
    int x=; char ch=readc();
    while (!isdigit(ch)) ch=readc();
    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
    return x;
}
iv writec(int x){ if (x>) writec(x/); putchar(x%+); }
iv _write(int x){ writec(x),putchar('\n'); }
iv pshp(int x){ t[x].p=t[t[x].to[]].p^t[t[x].to[]].p^a[x]; }
iv pshd(int x){
    if (t[x].f){
        int &l=t[x].to[],&r=t[x].to[];
        t[l].f^=,t[r].f^=,t[x].f=,swap(l,r);
    }
}
il bool rt(int x){ return t[t[x].fa].to[]!=x&&t[t[x].fa].to[]!=x; }
iv rtt(int x){
    int y=t[x].fa,z=t[y].fa,l=(t[y].to[]==x);
    if (!rt(y)) t[z].to[t[z].to[]!=y]=x;
    t[x].fa=z,t[y].fa=x,t[t[x].to[l^]].fa=y;
    t[y].to[l]=t[x].to[l^],t[x].to[l^]=y;
    pshp(y),pshp(x);
}
iv splay(int x){
    stk[tp=]=x;
    for (int i=x;!rt(i);i=t[i].fa) stk[++tp]=t[i].fa;
    for (int i=tp;i;i--) pshd(stk[i]);
    while (!rt(x)){
        int y=t[x].fa,z=t[y].fa;
        if (!rt(y)) if ((t[y].to[]==x)^(t[z].to[]==y)) rtt(x); else rtt(y);
        rtt(x);
    }
}
iv ccss(int x){ for (int i=;x;i=x,x=t[x].fa) splay(x),t[x].to[]=i,pshp(x); }
iv mkrt(int x){ ccss(x),splay(x),t[x].f^=; }
iv lnk(int x,int y){ mkrt(x),t[x].fa=y; }
iv sprt(int x,int y){ mkrt(x),ccss(y),splay(y); }
iv cut(int x,int y){ sprt(x,y); if (t[y].to[]==x) t[y].to[]=t[x].fa=; }
il int find(int x){ ccss(x),splay(x); while (t[x].to[]) x=t[x].to[]; return x; }
int main(){
    n=_read(),m=_read();
    for (int i=;i<=n;i++) a[i]=t[i].p=_read();
    while (m--){
        int flag=_read(),x=_read(),y=_read(),fx,fy;
        switch (flag){
            case : sprt(x,y),_write(t[y].p); break;
            case : fx=find(x),fy=find(y); if (fx!=fy) lnk(x,y); break;
            case : fx=find(x),fy=find(y); if (fx==fy) cut(x,y); break;
            case : ccss(x),splay(x),a[x]=y,pshp(x); break;
        }
    }
    return ;
}