题解 P3690 【【模板】Link Cut Tree （动态树）】

attack

2018-05-01 14:37:41

题解

更好的阅读体验点这里

前置知识

必须要理解splay
最好学过树链剖分

基础定义

LCT是一种解决动态树问题的方法，由tarjan~~(为什么又是他)~~在1982年提出，最原始的论文在这里,在论文中，tarjan除了介绍了均摊复杂度为O(log^2n)的LCT之外，还介绍了一种严格O(log^2n)的算法，不过本人太弱了，看不懂tarjan讲了些啥，也没找到其他的学习资料，因此这种算法我们不做讨论

能够解决的问题

求LCA
求最小生成树
维护链上信息(最大最小，链上和等)
维护联通性
维护子树信息(需要配合AAA树)
优化单纯性算法，在O(mnlog(n))的复杂度下求最大流（这两个是tarjan在它的论文最开头提到的，但是我除了在一本书中看到过有关的简介(没有代码)之外，再没看到过关于它的任何资料，）

构造

在解决树上问题的时候，有一种非常常见的操作叫做链剖分

链剖分一般分为三种

重链剖分，也就是我们常提到的“树剖”，剖分的原理是把节点个数最多的儿子当做重儿子
长链剖分，并不是很常见，可以O(1)求k级祖先，原理是把深度最深的儿子当做重(长)儿子
实链剖分，也就是LCT所用到的剖分方法，这里重点介绍一下

在实链剖分时，选择一个儿子作为重儿子，把连接这两个节点的边作为重边，连接其他儿子的边作为轻边。

与前两种剖分不同的是，实链剖分中的重儿子是可以不断变化的，因此在整棵树中的重链和轻链也是在不断变化的，这就需要我们用更灵活一些的数据结构来维护。

维护一条链，我们首先可以想到的是链表，但是用链表来维护树上权值和的话时间复杂度肯定是O(n^2)的，即使是块状链表也只能做到O(n \sqrt{n})

因此我们用平衡树来维护链上信息，那么用什么平衡树呢？理论上splay和fhq treap都是可以的，treap不可以，因为不能维护翻转信息，在这里我比较推荐splay，因为网上有关LCT的题目大多数题解都是用splay写的，这样的话学习难度也会小一点，而且我自测splay的常数要比fhq treap小很多

我们用splay维护每一条实路径(仅由实边组成的路径)，因为每条实路径都对应一条从根节点出发的链，这样的话路径上每个节点的深度都是不同的，因此在splay中，我们按深度作为关键字，对于一个节点，它的左孩子所对应的原节点深度比它小，右儿子所对应的原节点深度比它大

（这里插一句闲话，LCT之所以难于理解，很大程度上是初学者分不清原树/splay，因此我希望大家在继续往下读的过程中，一定要分清楚我所说的概念到时指的是原树还是splay树）

但是这样的话，虽然每个节点都包含在了splay中，但是每个splay之间都是独立的，因此我们要考虑如何在各个splay中建立联系，对于一个节点，假设它有三个儿子，其中最多有一个节点可以和他在一个splay中，另外两个儿子分别属于不同的splay。这里有一个非常巧妙的性质——另外两个儿子在他们所在的子树中一定是深度最小的，因此我们可以让每个splay中的根节点指向splay中中序遍历编号最小(也就是原树中深度最小)的节点的父亲，有点绕，希望大家好好理解一下

对于一棵这样的树 (图片来源：FlashHu的博客)

它的splay树可能长这个样子

LCT基础操作

access(x)

将根节点到x点的路径变为实路径，且x与其儿子之间的边都变为虚边。

首先考虑一下这个操作有什么目的，有了这个操作，我们就可以将根节点到x的这条路径放在同一棵splay中，这样可以很方便通过在splay上打标记得到路径信息

具体怎么实现呢？

还是上面那张图

如果我们要执行access(N)，

我们可以从下往上依次处理，首先我们要使得N-O这条边变为轻边，因为在splay中，节点的深度是唯一的，所以我们首先把N，转到根节点，这样它右边的节点一定是O，然后直接把N节点的右儿子置为0就可以了

继续往上，我们需要使I-K这条边变为轻边，同时使I-L这条边变为重边

考虑如何使I-K变为轻边。和上面的思路一样，我们首先使I转到所在splay的根节点，这样的话它的右儿子一定是K，然后我们只需要断开I-K这条边即可

考虑如何使I-L变为重边。这个就so easy了，直接将I的右儿子置为L即可

此时I所在的splay的父亲指向H

继续往上思路就是一样的了，按照同样的套路使得H-J变为轻边，使H-I变为重边，

此时H指向A，然后让A转到所在splay的根节点，把右儿子置为H即可

这样我们就实现了access操作，按照上面的流程，我们不难总结出算法框架

将要处理的节点转到根
更改右儿子
更新标记

代码的话，，首先说一下各种定义

struct node {
    int f, ch[2], s;
    //f：父亲
    //ch[0]/[1]:左/右儿子
    //s:标记，依题目而变
    bool r;//是否翻转
}T[MAXN];

access

void access(int x) {//访问x节点 
    for(int y = 0; x; x = fa(y = x))
        splay(x), rs(x) = y, update(x);
    //首先把x splay到所在平衡树的根，这样可以保证它的右孩子就是在原树中对应的重链(右孩子深度比它大)
    //y是splay中x的儿子，把x的右儿子改成y，也就是把x和y之间的边变成实边
    //更改了节点顺序，需要update 
}

makeroot(x)

将x变为原树的根

考虑这个操作的意义。对于大多数树上询问来说，都是询问一条过根节点的路径，由于LCT的构造的缘故，这种询问处理起来非常麻烦。但是当询问的一端在根节点的时候，处理起来就容易的多，所以这个操作的意义在于帮助我们更好的处理询问

这里有一个非常巧妙的实现思路：

首先我们需要access(x)，这样我们就把根节点和x放到了同一棵splay中

此时x是不含右儿子的（没有深度比他大的点）

然后我们需要splay(x)，此时x会成为splay的根节点，且x不含右儿子。

但是在根节点所在的splay中，根节点没有左儿子（没有深度比他小的节点）

这可怎么办呢？？

这里就有一个骚操作了，我们直接将x的左右子树翻转！

这样x不就没有左儿子了么？233

事实证明这样是对的

代码：

void makeroot(int x) {//把x改为原树的根节点 
    access(x);
    splay(x);
    T[x].r ^= 1;//更新翻转标记
}

findroot(x)

找到x所在原树的根

你刚开始可能跟我一样很呆萌的认为：x所在原树的根不就是根节点么？

但是。。

有一点需要注意：LCT维护的是森林，也就是很多棵树，因此每个节点所在原树的根节点往往是不同的

考虑这个操作的意义：

大家有没有发现，这个操作跟并查集中找祖先的操作很类似？没错，这个操作的用处就是判断两个节点的联通性（是否在同一棵树上）

实现的话，我们利用了一个性质：一棵树的根节点一定是深度最小的点

这样我们先accexx(x)，然后splay(x)，再不断的往左走，这样就可以找到x所在树的根节点了！

注意！往左走的时候一定要下传标记，否则在某些题目中你会挂的很惨！

代码

int findroot(int x) {//找到x在原树中的根节点 
    access(x);splay(x);
    pushdown(x);
    while(ls(x)) pushdown(x = ls(x));//找到深度最小的点即为根节点 
    return x;
}

split(x,y)

获取到x-y所对应的路径，

这个操作的意义就非常显然了

实现也非常好想，直接上代码吧

这样的话可以通过访问y节点来获取到有关路径的信息

void split(int x, int y) {
    makeroot(x);//首先把x置为根节点 
    access(y); splay(y);
    //然后访问一下y，再把y转到根节点，这样y维护的就是x - y 路径上的信息 
}

link(x,y)

连接x,y

这个操作的意义也很显然

首先我们需要makeroot(x)，然后access(y),splay(y)，最后把x的父亲指向y就可以

注意在一些毒瘤题中不保证x,y未联通，这样还需要判断一下联通性

void link(int x, int y) {
    makeroot(x);//把x置为根节点 
    if(findroot(y) != x ) fa(x) = y;
    //如果x与y不在同一个splay中，就把y置为x的父亲 
    //findroot(y)的时候已经执行了access(y),splay(y)
}

cut(x,y)

断开x-y这条边

意义也非常显然

实现的话看上去比较容易

我们需要split(x,y)，此时x的父亲是y，y因为是深度最深的点，所以它的左儿子是x，

然后断绝父子关系就好了

但是！！，如果出题人不保证x-y相连呢？？

如果仍然这样改的话整棵树就乱了

因此我们还要加一坨判断

首先x,y一定要在一棵树内
x$的父亲是$y$，且$y$的左儿子是$x
这两个比较显然

这个可能就不是那么显然了

我们仔细考虑一下，x的右儿子代表着深度比他大的节点，y的左儿子代表着深度比他小的节点

那如果出现这种情况呢？

然后我们就GG了，

或者你可以试试这组数据

5 6 1 2 3 4 5
1 1 2
1 2 3
1 3 4
1 4 5
2 1 5
0 1 5

因此我们有必要加上这个判断

代码：

void cut(int x, int y) {
    makeroot(x);
    if(findroot(y) == x && fa(x) == y && ls(y) == x && !rs(x)) { 
        fa(x) = T[y].ch[0] = 0;
        update(y);
    }
}

时间复杂度

以上操作的平摊复杂度均为O(log^2N)

具体的证明可以参考YangZhe的论文

小结

LCT的操作也就是这么多了，

不过LCT有很多拓展，题目类型也有很多，大部分我还没做过

等以后慢慢整理吧

洛谷的板子题代码：

其中的splay和rotate都是我自己yy的，并不是很主流的写法，不过跑的比较快

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define swap(x,y) x ^= y, y ^= x, x ^= y
const int MAXN=3 * 1e5 + 10;
inline int read()
{
    char c = getchar();int x = 0,f = 1;
    while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
    return x * f;
}
#define fa(x) T[x].f
#define ls(x) T[x].ch[0]
#define rs(x) T[x].ch[1]
int v[MAXN];
struct node {
    int f, ch[2], s;
    bool r;
}T[MAXN];
int ident(int x) {
    return T[fa(x)].ch[0] == x ? 0 : 1;//判断该节点是父亲的哪个儿子 
}
int connect(int x,int fa,int how) {
    T[x].f=fa;
    T[fa].ch[how]=x;//连接 
}
inline bool IsRoot(int x) {//若为splay中的根则返回1 否则返回0 
    return ls( fa(x) ) != x && rs( fa(x) ) != x;
    //用到了两个性质
    //1.若x与fa(x)之间的边是虚边，那么它的父亲的孩子中不会有他（不在同一个splay内）
    //2. splay的根节点与其父亲之间的边是虚边 
}
void update(int x) {
    T[x].s = T[ls(x)].s ^ T[rs(x)].s ^ v[x];//维护路径上的异或和 
}
void pushdown(int x) {
    if(T[x].r) {
        swap(ls(x),rs(x));
        T[ls(x)].r ^= 1;
        T[rs(x)].r ^= 1;
        T[x].r = 0;//标记下传 
    }
}
void rotate(int x) {
    int Y = T[x].f, R = T[Y].f, Yson = ident(x), Rson = ident(Y);
    int B = T[x].ch[Yson ^ 1];
    T[x].f = R;
    if(!IsRoot(Y))
        connect(x, R, Rson);
    //这里如果不判断y是否根节点，那么当y是根节点的时候，0节点的儿子就会被更新为x
    //这样x就永远不能被判断为根节点，也就会无限循环下去了
    //但是这里不更新x的父亲的话就会出现无限递归的情况 
    connect(B, Y, Yson);
    connect(Y, x, Yson ^ 1);
    update(Y); update(x);
}
int st[MAXN];
void splay(int x) {
    int y = x, top = 0;
    st[++top] = y;
    while(!IsRoot(y)) st[++top] = y = fa(y);
    //用一个栈维护所有的标记
    while(top) pushdown(st[top--]);
    //因为在旋转的时候不会处理标记，所以splay之前应该下传所有标记 
    for(int y = fa(x); !IsRoot(x); rotate(x), y = fa(x))//只要不是根就转 
        if(!IsRoot(y)) 
            rotate( ident(x) == ident(y) ? x : y );
}
void access(int x) {//访问x节点 
    for(int y = 0; x; x = fa(y = x))
        splay(x), rs(x) = y, update(x);
}
void makeroot(int x) {//把x改为原树的根节点 
    access(x);
    splay(x);
    T[x].r ^= 1;
    pushdown(x);
}
int findroot(int x) {//找到x在原树中的根节点 
    access(x);splay(x);
    pushdown(x);
    while(ls(x)) pushdown(x = ls(x));//找到深度最小的点即为根节点 
    return x;
}
void split(int x, int y) {
    makeroot(x);//首先把x置为根节点 
    access(y); splay(y);
}
void link(int x, int y) {
    makeroot(x);//把x置为根节点 
    if(findroot(y) != x ) fa(x) = y;
}
void cut(int x, int y) {
    makeroot(x);
    if(findroot(y) == x && fa(x) == y && ls(y) == x && !rs(x)) { 
        fa(x) = T[y].ch[0] = 0;
        update(y);
    }
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    #else
    #endif
    int N = read(), M = read();
    for(int i = 1; i <= N; i++) v[i] = read();
    for(int i = 1; i <= M; i++) {
        int opt = read(), x = read(), y = read();
        if(opt == 0) split(x, y), printf("%d\n",T[y].s);
        else if(opt == 1) link(x, y);
        else if(opt == 2) cut(x, y);
        else if(opt == 3) splay(x), v[x] = y;
    }
    return 0;
}

参考资料

FlashHu的博客

YangZhe-QTREE解法的一些研究

《高级数据结构》-林厚从