Link Cut Tree 学习笔记

Published on 2016-03-29

学 LCT 之前，建议先学习树链剖分，看看 qzc 的 论文，最好对树的链状结构深刻的印象。
预备知识显然有 Splay，要会打各种标记，打熟练，不然 LCT 是很难快速写对的。
然后就可以直接看 QTREE解法的一些研究，我这里写一下我在学习中／大家可能遇到的一些问题。

相关问答

理解：
Q：Link Cut Tree 是什么？
A：LCT 用 Splay 维护树链，由于 Splay 的可分裂合并性，LCT 可维护动态的树链，即支持对树边进行修改。

Q：Link Cut Tree 可以干什么？
A：不严谨的说，LCT 可以进行 Link（加边），Cut（删边）操作，由于我们用 Splay 维护树链，所以可以对树上路径进行查询。

Q：Preferred Path 是什么？
A：我们访问任何节点 uu，用 Access 操作把根到 uu 的路径变为主链，这个主链被称为 Preferred Path。

Q：树的根是谁？
A：如果不联通，就是森林，即使联通，树的根是谁不重要，因为根随时可能会变，我们也可以很快速的变换树根。

实现部分：
Q：每一棵 Splay 树随时在变，那么一棵 Splay 树的根是谁呢？怎么记录？
A：由于树链的数量，长度均在变化，我们不记录有多少树链，也不记录树链的大小，我们只记录节点的关系，即节点的 fa,leftChild,rightChild\text{fa},\text{leftChild},\text{rightChild}，如果一个节点的 fa\text{fa} 为 null\text{null} 或者它的 fa\text{fa} 左右儿子都不是它（此时 fa\text{fa} 是 Path Parent），的那么就短暂的作为这棵 Splay 的根。

Q：既然有很多 Splay，随时在变，我怎么将一个节点旋转的根？怎么知道一个节点属于哪一棵 Splay 树呢？
A：如果你的 Splay 是自底向上的写法，你一定知道怎么处理（几乎没什么不同），如果你跟我一样是自顶向下的写法，要注意，由于我们记录了 fa\text{fa} 指针，我们可以顺着 fa\text{fa} 指针向上爬，边爬边记录是从哪个儿子爬上去的，一直爬到根，再进行 splay。这个过程很像不记录表头的双向链表，我们每一次手动爬到表头，再操作。为什么要这样呢？因为一条链，随时有可能接到新的链上面去，我们不可能对所有的节点属于哪条链进行修改。

Q：Path Parent 是怎么记录的，它跟 Splay 中节点的 fa\text{fa} 指针有关系吗？
A：Path Parent 指的是链与链之间的轻边，它永远记录在每棵 Splay 任意时刻的根上面，它不是 Splay 之间链接节点的边。由于 Splay 是按 deep 为关键字排序的，所以可以看作为深度最浅的节点在树中指向其父亲的边。而 Splay 之间链接节点的边，不一定是树边，如果把 Splay 想象成序列 a0,a1,a2,...,ana_0, a_1, a_2,...,a_n，那么显然有树边 (ai,ai+1)(i<n)(a_i,a_{i + 1})(i < n)。

剩下就是 LCT 的各种操作，我想只要有了 Access 和 Splay 和 MakeRoot，绝对是不难的。

习题

学了一个算法，不能不做题，下面扔几道模版 LCT 题，供大家参考。由于我的 Splay 是从上往下，训练指南的版本，相比网上大部分可能有所不同，但自认为比较简洁。

BZOJ 1180 & 2843

题目地址
很裸的题，还双倍经验。

//  Created by Sengxian on 3/28/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1180 LCT
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <ctime>
#include <stack>
using namespace std;
const int maxn = 30000 + 10, INF = 0x3f3f3f3f;

inline int ReadInt() {
    int ch = getchar(), n = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

struct Splay *null;
struct Splay {
    Splay *fa, *ch[2];
    int val, sum, c;
    bool reversed;
    Splay() {}
    Splay(int val): fa(null), val(val), sum(val), reversed(false) {ch[0] = ch[1] = null;}
    inline void maintain() {if (this != null) this -> sum = ch[0] -> sum + ch[1] -> sum + val;}
    inline void reverse() {if (this != null) reversed ^= 1, swap(ch[0], ch[1]), c = c == -1 ? -1 : 1 - c;}
    inline void pushdown() {if (reversed) reversed = 0, ch[0] -> reverse(), ch[1] -> reverse();}
}pool[maxn];

inline void rotate(Splay* &o, int d) {
    Splay *k = o -> ch[d ^ 1];
    k -> ch[d] -> fa = o, k -> fa = o -> fa, o -> fa = k;
    o -> ch[d ^ 1] = k -> ch[d], k -> ch[d] = o;
    o -> maintain(), k -> maintain();
    o = k;
}

void _splay(Splay* &o) {
    o -> pushdown();
    if (o -> c != -1) {
        Splay *k = o -> ch[o -> c];
        k -> pushdown();
        if (k -> c != -1) {
            _splay(k -> ch[k -> c]);
            if (o -> c == k -> c) rotate(o, o -> c ^ 1); else rotate(o -> ch[o -> c], o -> c);
        }
        rotate(o, o -> c ^ 1);
    }
}

inline bool isRoot(Splay *o) {
    return o -> fa == null || (o -> fa -> ch[0] != o && o -> fa -> ch[1] != o);
}

//将节点 u 旋转到所在 splay 的根节点
void splay(Splay *o) {
    o -> c = -1;
    while (!isRoot(o)) {
        if (o == o -> fa -> ch[0]) o -> fa -> c = 0;
        else o -> fa -> c = 1;
        o = o -> fa;
    }
    _splay(o);
}

Splay* access(Splay *o) {
    Splay *k = null;
    while (o != null) {
        splay(o);
        o -> ch[1] = k;
        o -> maintain();
        k = o;
        o = o -> fa;
    }
    while (k -> ch[0] != null) k = k -> ch[0];
    return k;
}

inline void makeRoot(Splay *x) {
    access(x);
    splay(x);
    x -> reverse();
}

inline void link(int x, int y) {
    makeRoot(pool + x);
    (pool + x) -> fa = pool + y;
}

inline bool connected(int x, int y) {
    return access(pool + x) == access(pool + y);
}

inline int Distance(int x, int y) {
    makeRoot(pool + x), access(pool + y), splay(pool + y);
    return (pool + y) -> sum;
}

int n;
char oper[10];
int main() {
    null = new Splay(), null -> val = null -> sum = 0;
    n = ReadInt();
    for (int i = 0; i < n; ++i) {
        pool[i].fa = null, pool[i].ch[0] = pool[i].ch[1] = null;
        pool[i].sum = pool[i].val = ReadInt();
        pool[i].reversed = false;
    }
    int q = ReadInt();
    while (q--) {
        scanf("%s", oper);
        int x = ReadInt() - 1;
        if (oper[0] == 'b') { //判断联通
            int y = ReadInt() - 1;
            if (connected(x, y)) puts("no");
            else puts("yes"), link(x, y);
        }else if (oper[0] == 'p') { //修改权值
            splay(pool + x);
            (pool + x) -> val = ReadInt();
            (pool + x) -> maintain();
        }else if (oper[0] == 'e') { //求路径和
            int y = ReadInt() - 1;
            if (connected(x, y)) printf("%d\n", Distance(x, y));
            else puts("impossible");
        }
    }
    return 0;
}

BZOJ 2002

题目地址
加一个节点即可，也是裸题。

//  Created by Sengxian on 3/28/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2002 LCT
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <ctime>
#include <stack>
using namespace std;
const int maxn = 200000 + 10;

inline int ReadInt() {
    int ch = getchar(), n = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

struct Splay *null;
struct Splay {
    Splay *fa, *ch[2];
    int s, c; bool reversed;
    inline void maintain() {if (this != null) this -> s = ch[0] -> s + ch[1] -> s + 1;}
    inline void reverse() {if (this != null) swap(ch[0], ch[1]), reversed ^= 1, c = c == -1 ? -1 : 1 - c;}
    inline void pushdown() {if (reversed) reversed = false, ch[0] -> reverse(), ch[1] -> reverse();}
    inline bool isRoot() {return (fa == null || (fa -> ch[0] != this && fa -> ch[1] != this));}
}pool[maxn];

inline void rotate(Splay* &o, int d) {
    Splay *k = o -> ch[d ^ 1];
    k -> fa = o -> fa, o -> fa = k, k -> ch[d] -> fa = o;
    o -> ch[d ^ 1] = k -> ch[d], k -> ch[d] = o;
    o -> maintain(), k -> maintain();
    o = k;
}

void _splay(Splay* &o) {
    o -> pushdown();
    int d = o -> c;
    if (d != -1) {
        Splay *p = o -> ch[d];
        int d2 = p -> c;
        p -> pushdown();
        if (d2 != -1) {
            _splay(p -> ch[d2]);
            if (d == d2) rotate(o, d ^ 1); else rotate(o -> ch[d], d);
        }
        rotate(o, d ^ 1);
    }
}

void splay(Splay* o) {
    o -> c = -1;
    while (!o -> isRoot()) {
        if (o -> fa -> ch[0] == o) o -> fa -> c = 0;
        else o -> fa -> c = 1;
        o = o -> fa;
    }
    _splay(o);
}

Splay *access(Splay* o) {
    Splay *k = null;
    while (o != null) {
        splay(o);
        o -> ch[1] = k;
        o -> maintain();
        k = o;
        o = o -> fa;
    }
    while (k -> ch[0] != null) k = k -> ch[0];
    return k;
}

inline void makeRoot(Splay *o) {
    access(o);
    splay(o);
    o -> reverse();
}

inline Splay *c(int x) {return pool + x;}

inline int dis(int x, int y) {
    makeRoot(c(x)), access(c(y)), splay(c(y));
    return c(y) -> s;
}

inline void link(int x, int y) {
    makeRoot(c(x));
    c(x) -> fa = c(y);
}

inline void cut(int x, int y) {
    makeRoot(c(x)), access(c(y)), splay(c(x));
    c(x) -> ch[1] -> fa = null;
    c(x) -> ch[1] = null;
    c(x) -> maintain();
}

inline bool connected(int x, int y) {
    return access(pool + x) == access(pool + y);
}

int n, kv[maxn];

int main() {
    null = new Splay(), null -> s = 0;
    n = ReadInt();
    for (int i = 0; i <= n; ++i) {
        pool[i].fa = pool[i].ch[0] = pool[i].ch[1] = null;
        pool[i].s = 1, pool[i].reversed = false;
        if (i < n) kv[i] = ReadInt();
    }
    for (int i = 0; i < n; ++i) link(i, min(n, i + kv[i]));
    int m = ReadInt();
    while (m--) {
        int oper = ReadInt(), u = ReadInt();
        if (oper == 1) printf("%d\n", dis(u, n) - 1);
        else if (oper == 2) {
            cut(u, min(n, u + kv[u]));
            link(u, min(n, u + (kv[u] = ReadInt())));
        }else assert(false);
    }
    return 0;
}

BZOJ 2631

题目地址
后面会专门写题解，核心在标记。

BZOJ 2049

题目地址
裸题。

BZOJ 3282

题目地址
异或有交换律，所以直接搞就行。

BZOJ 3110 - [Zjoi2013]K大数查询