Link Cut Tree 学习笔记

发表于 | 分类于 | 博文状态：更新中 | 阅读次数：

加边，删边，询问之中怎料变幻无常；

左旋，右旋，伸展背后暗含均摊平衡。

LCT 简介

Link Cut Tree 是解决动态树相关问题的有力工具，其实准确说是维护动态的有根森林，即多棵有根树。它支持在均摊 $O(\log n)$ 的时间对森林进行以下操作：

  • newnode(x) 新建节点 x，这是个平凡的操作，是 $O(1)$ 的。
  • link(x, y) 将在不同连通块的节点 x 和 y 之间连边。
  • cut(x, y) 将 x, y 之间已有的边删掉。
  • makeRoot(x) 让 x 成为其所在树的根。
  • pathQuery(x, y) 或 pathModify ，询问 x 到 y 的路径上的有结合律的信息（如路径长度，路径上节点的异或和等可以用线段树维护的信息），或者进行修改。

LCT 核心操作

Link Cut Tree 的核心是每个节点记录一个重儿子 (preferred child，应该叫偏爱儿子)，节点到重儿子的边称为重边，相邻的重边形成的叫重链，LCT 要把每个重链以深度为关键字用一棵 Splay 树来维护，而各个 Splay 树之间也存在父子关系，。具体说：

Auxiliary Tree(辅助树)

  • 由一条重链上的所有节点所构成的 Splay 称作这条链的辅助树

  • 每个点的键值为这个点的深度，即这棵Splay的中序遍历是这条链从链顶到链底的所有节点构成的序列

  • 辅助树的根节点的父亲指向链顶的父亲节点，然而链顶的父亲节点的儿子并不指向辅助树的根节点

  • （也就是说父亲不认轻儿子只认重儿子，儿子都认父亲）

  • 这条性质为后来的操作提供了依据

原树与辅助树的关系

  • 原树中的重链 -> 辅助树中两个节点位于同一棵Splay中
  • 原树中的轻链 -> 辅助树中子节点所在Splay的根节点的father指向父节点
  • 注意原树与辅助树的结构并不相同
  • 辅助树的根节点≠原树的根节点
  • 辅助树中的father≠原树中的father

辅助树是不断变化的，重链和轻链不断变化

令每个节点的重儿子 $h_v$ 如下：
$$
h_v = \begin{cases}v & \text{if }v\text{ is the last accessed vertex in its subtree}\
w &\text{if the last accessed vertex in }v \text{ ‘s subtree is in }\&w \text{‘s subtree} \end{cases}
$$
只要维护上这个，就可以解决上面不涉及换根的所有问题了。

换根怎么解决呢？

实现

点击显示/隐藏代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/*
 * Author       : YangDavid
 * Created Time : 2020年03月25日 星期三 18时09分40秒
 * Code Time    : 2020年03月25日 星期三 19时32分52秒
 */

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

struct LCT {
#define sid(x) ((x) == ch[fa[x]][1])
#define nroot(x) ((x) == ch[fa[x]][0] || (x) == ch[fa[x]][1])
    vector<int> fa, xorsum, wg, rev;
    vector<array<int,2>> ch;
    LCT(int n=0): fa(n+1), xorsum(n+1), wg(n+1), rev(n+1), ch(n+1) { }
    int newnode(int val) {
        fa.push_back(0), xorsum.push_back(val), wg.push_back(val);
        rev.push_back(0), ch.push_back(array<int,2>({0,0}));
        return fa.size() - 1;
    }
    void up(int o) {
        if(!o) return;
        xorsum[o] = xorsum[ch[o][0]] ^ xorsum[ch[o][1]] ^ wg[o];
    }
    void down(int o) {
        if(o && rev[o]) {
            swap(ch[o][0], ch[o][1]);
            rev[ch[o][0]] ^= 1;
            rev[ch[o][1]] ^= 1;
            rev[o] = 0;
        }
    }
    void update(int x) {
        if(nroot(x)) update(fa[x]);
        down(x);
    }
    void rotate(int x) {
        int y = fa[x], z = fa[y], k = sid(x);
        if(nroot(y)) ch[z][sid(y)] = x;
        fa[x] = z;
        fa[ch[x][k^1]] = y, ch[y][k] = ch[x][k^1];
        fa[y] = x, ch[x][k^1] = y;
        up(y), up(x);
    }
    void splay(int x) { // never splay(0)!!!
        update(x);
        for(int f = fa[x]; nroot(x); rotate(x), f = fa[x]) {
            if(nroot(f)) rotate(sid(x) == sid(f) ? f : x);
        }
    }
    int access(int x) { // root-to-x path became preferred, x became root.
        int p = 0, ori = x;
        for(; x; p = x, x = fa[x])
            splay(x), ch[x][1] = p, up(x);
        splay(ori);
        return p;
    }
    void makeRoot(int x) {
        access(x);
        rev[x] ^= 1;
    }
    void link(int x, int y) { // root(x) != root(y) must hold!
        makeRoot(x);
        fa[x] = y;
    }
    void cut(int x, int y) { // edge must exist!
        makeRoot(x);
        access(y);
        ch[y][0] = fa[x] = 0;
        up(y);
    }
    int findRoot(int x) {
        access(x);
        for(;;) {
            down(x);
            if(!ch[x][0]) break;
            x = ch[x][0];
        }
        splay(x);
        return x;
    }
    int query(int x, int y) {
        makeRoot(x);
        access(y);
        return xorsum[y];
    }
    void modify(int u, int w) {
        access(u);
        wg[u] = w;
        up(u);
    }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    LCT lct;
    set<pii> edges;
    for(int i = 1; i <= n; ++i) {
        static int x; scanf("%d", &x);
        lct.newnode(x);
    }
    for(int i = 1; i <= m; ++i) {
        static int op, u, v;
        scanf("%d%d%d", &op, &u, &v);
        if(op == 0) {
            printf("%d\n", lct.query(u, v));
        } if(op == 1) {
            if(u > v) swap(u, v);
            if(lct.findRoot(u) != lct.findRoot(v))
                lct.link(u, v), edges.emplace(u, v);
        } else if(op == 2) {
            if(u > v) swap(u, v);
            if(!edges.count({u, v})) continue;
            lct.cut(u, v);
        } else if(op == 3) {
            lct.modify(u, v);
        }
    }

    return 0;
}

时间复杂度分析：

$m$ 次操作，$h_v$ 的所有改变次数加起来是 $O(m\log n)$ 的。这是因为：
$$
\begin{aligned}
\text{changes in }h_v \leq & \text{ preferred light edge created} + \
& \text{ preferred heavy edge destroyed} +\
& \text{ } n-1
\end{aligned}
$$

Access Lemma

轻重链剖分