跳转至

Link Cut Tree

P3690 【模板】动态树（LCT）

给定 \(n\) 个点以及每个点的权值，要你处理接下来的 \(m\) 个操作。 操作有四种，操作从 \(0\) 到 \(3\) 编号。点从 \(1\) 到 \(n\) 编号。

  • 0 x y 代表询问从 \(x\) 到 \(y\) 的路径上的点的权值的 \(\text{xor}\) 和。保证 \(x\) 到 \(y\) 是联通的。
  • 1 x y 代表连接 \(x\) 到 \(y\)，若 \(x\) 到 \(y\) 已经联通则无需连接。
  • 2 x y 代表删除边 \((x,y)\)，不保证边 \((x,y)\) 存在。
  • 3 x y 代表将点 \(x\) 上的权值变成 \(y\)。

对于全部的测试点，保证：

  • \(1 \leq n \leq 10^5\)， \(1 \leq m \leq 3 \times 10^5\)， \(1 \leq a_i \leq 10^9\)。
  • 对于操作 \(0, 1, 2\)，保证 \(1 \leq x, y \leq n\)。
  • 对于操作 \(3\)，保证 \(1 \leq x \leq n\)， \(1 \leq y \leq 10^9\)。

用途

LCT(Link Cut Tree) 是一种用于处理一个有根的森林中各棵树之间的动态操作。LCT 能维护动态树的的平衡性，以 \(O(\log n)\) 的均摊复杂度进行合并、删除、查询等操作。

LCT 的思想

LCT 结合了树链剖分和 Splay 树的思路。其核心思想为 “原树实链从上到下，对应 Splay 树从左到右”。

  1. 实链剖分
  2. 转换原树为辅助树，用辅助树维护原树，在代码中只需维护辅助树。
  3. LCT 借用了 Splay 树的操作方法处理实链。

从原树到辅助树

  1. 将原树剖分为实链和虚边
  2. 将原树转换为为辅助树，实链和虚边
  3. 用 Splay 树处理实链（节点在 Splay 中的优先级为原树上节点的深度）

转化为

LCT 的性质

  1. 辅助树表达原树的路径形态。
  2. 原树的一条实链对应辅助树上的一颗 Splay 树。
  3. 原树实链从上到下，对应 Splay 树从左到右。
  4. 辅助树中的各棵 Splay 树用虚边链接。

LCT 的操作

  1. isrt(x) ：判断 \(x\) 是否为它所在的 Splay 树的根。

    实现 
    1
2
3
4
5
    bool isrt(int x)
{
    int g = t[x].fa;
    return t[g].son[0] != x && t[g].son[1] != x;
}

  2. splay(x) ：将辅助树的节点 \(x\) 转到其所在 Splay 树的根，操作并不影响原树。

    实现 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    void splay(int x)
{
    int y, z;
    update(x);
    while (!isrt(x))
    {
        y = t[x].fa, z = t[y].fa;
        if (!isrt(y))
        {
            if ((t[z].son[0] == y) ^ (t[y].son[0] == x))
                rotate(x);
            else
                rotate(y);
        }
        rotate(x);
    }
    pu(x);
}

  3. access(x) ：在原树上创建一条从根到节点 \(x\) 的实链，即辅助树上一颗 Splay。

    实现 
    1
2
3
4
5
6
7
8
9
    void access(int x)
{
    for (int s = 0; x; s = x, x = t[x].fa)
    {
        splay(x);
        rs = s;
        pu(x);
    }
}

  4. makert(x) ：把 \(x\) 在原树上旋转到根的位置。

    实现 
    1
2
3
4
5
6
    void makert(int x)
{
    access(x);
    splay(x);
    reverse(x);
}

  5. findrt(x) ：查找 \(x\) 在原树上的根，常用于判断两节点是否连通。

    实现 
    1
2
3
4
5
6
7
    int findrt(int x)
{
    access(x);
    splay(x);
    while (ls) update(x), x = ls;
    return x;
}

  6. split(x, y) ：在原树上生成一条 \(x\) 到 \(y\) 的实链。

    实现 
    1
2
3
4
5
6
    void split(int x, int y)
{
    makert(x);
    access(y);
    splay(y);
}

  7. link(x, y) ：连接 \(x\) 和 \(y\)。

    实现 
    1
2
3
4
5
    void link(int x, int y)
{
    makert(x);
    t[x].fa = y;
}

  8. cut(x, y) ：断开 \(x\) 和 \(y\)。

    实现 
    1
2
3
4
5
6
7
    void cut(int x, int y)
{
    split(x, y);
    if (t[y].son[0] != x || rs) return;
    t[x].fa = t[y].son[0] = 0;
    pu(x);
}

总实现

实现 
  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
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 3e5 + 5;
struct node
{
    int fa, son[2], sum, val, tag;
} t[N];
#define ls t[x].son[0]
#define rs t[x].son[1]
bool isrt(int x)
{
    int g = t[x].fa;
    return t[g].son[0] != x && t[g].son[1] != x;
}
void pu(int x) { t[x].sum = t[x].val ^ t[ls].sum ^ t[rs].sum; }
void reverse(int x)
{
    if (!x) return;
    swap(ls, rs);
    t[x].tag ^= 1;
}
void pd(int x)
{
    if (t[x].tag)
    {
        reverse(ls);
        reverse(rs);
        t[x].tag = 0;
    }
}
void update(int x)
{
    if (!isrt(x)) update(t[x].fa);
    pd(x);
}
void rotate(int x)
{
    int y = t[x].fa;
    int z = t[y].fa;
    int k = (t[y].son[1] == x);
    if (!isrt(y)) t[z].son[t[z].son[1] == y] = x;
    t[x].fa = z;
    t[y].son[k] = t[x].son[k ^ 1];
    if (t[x].son[k ^ 1]) t[t[x].son[k ^ 1]].fa = y;
    t[y].fa = x;
    t[x].son[k ^ 1] = y;
    pu(y);
}
void splay(int x)
{
    int y, z;
    update(x);
    while (!isrt(x))
    {
        y = t[x].fa, z = t[y].fa;
        if (!isrt(y))
        {
            if ((t[z].son[0] == y) ^ (t[y].son[0] == x))
                rotate(x);
            else
                rotate(y);
        }
        rotate(x);
    }
    pu(x);
}
void access(int x)
{
    for (int s = 0; x; s = x, x = t[x].fa)
    {
        splay(x);
        rs = s;
        pu(x);
    }
}
void makert(int x)
{
    access(x);
    splay(x);
    reverse(x);
}
void split(int x, int y)
{
    makert(x);
    access(y);
    splay(y);
}
void link(int x, int y)
{
    makert(x);
    t[x].fa = y;
}
void cut(int x, int y)
{
    split(x, y);
    if (t[y].son[0] != x || rs) return;
    t[x].fa = t[y].son[0] = 0;
    pu(x);
}
int findrt(int x)
{
    access(x);
    splay(x);
    while (ls) update(x), x = ls;
    return x;
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i].val;
        t[i].sum = t[i].val;
    }
    while (m--)
    {
        int opt, a, b;
        cin >> opt >> a >> b;
        if (opt == 0)
        {
            split(a, b);
            cout << t[b].sum << endl;
        }
        if (opt == 1)
            if (findrt(a) != findrt(b)) link(a, b);
        if (opt == 2) cut(a, b);
        if (opt == 3) splay(a), t[a].val = b;
    }
    return 0;
}

LCT 的应用

  1. 判断连通性。
  2. 求两点距离。
  3. 求 LCA。

习题

P2147 [SDOI2008] 洞穴勘测

辉辉热衷于洞穴勘测。

某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由 \(n\) 个洞穴（分别编号为 \(1\) 到 \(n\)）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。 洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，\(123\) 号洞穴和 \(127\) 号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。

辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：

  • 如果监测到洞穴 \(u\) 和洞穴 \(v\) 之间出现了一条通道，终端机上会显示一条指令 Connect u v；

  • 如果监测到洞穴 \(u\) 和洞穴 \(v\) 之间的通道被毁，终端机上会显示一条指令 Destroy u v。

经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。

因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。 然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。

辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴 \(u\) 和洞穴 \(v\) 是否连通。现在你要为他编写程序回答每一次询问。 已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

\(100\%\) 的数据满足 \(n \leq 10000, m \leq 200000\)。

保证所有 Destroy 指令将摧毁的是一条存在的通道。

本题输入、输出规模比较大，建议c/c++选手使用scanf和printf进行I/O操作以免超时。

P4312 [COI 2009] OTOCI

不久之前，Mirko 建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了 \(n\) 座冰岛，并且提供观光服务。

当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。Mirko 的旅行社遭受一次重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。

Mirko 希望开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。这些冰岛从1到N标号。一开始时这些岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在 \([0, 1000]\) 之间。你的程序需要处理以下三种命令：

  • bridge u v：询问结点 \(u\) 与结点 \(v\) 是否连通。如果是则输出 no；否则输出 yes，并且在结点 \(u\) 和结点 \(v\) 之间连一条无向边。
  • penguins u x：将结点 \(u\) 对应的权值 \(w_u\) 修改为 \(x\)。
  • excursion u v：如果结点 \(u\) 和结点 \(v\) 不连通，则输出 impossible。否则输出结点 \(u\) 到结点 \(v\) 的路径上的点对应的权值的和。

共有 \(q\) 个操作。

对于 \(100\%\) 的数据，\(1 \le n \le 3 \times 10^4\)， \(1 \le q \le 3\times 10^5\) , \(0 \le w_i \le 1000\)。

P1501 [国家集训队] Tree II

一棵 \(n\) 个点的树，每个点的初始权值为 \(1\)。 对于这棵树有 \(q\) 个操作，每个操作为以下四种操作之一：

  • + u v c：将 \(u\) 到 \(v\) 的路径上的点的权值都加上自然数 \(c\)；
  • - u1 v1 u2 v2：将树中原有的边 \((u_1,v_1)\) 删除，加入一条新边 \((u_2,v_2)\)，保证操作完之后仍然是一棵树；
  • * u v c：将 \(u\) 到 \(v\) 的路径上的点的权值都乘上自然数 \(c\)；
  • / u v：询问 \(u\) 到 \(v\) 的路径上的点的权值和，将答案对 \(51061\) 取模。

对于 \(100\%\) 的数据，\(1\le n,q \le 10^5\)， \(0\le c \le 10^4\)。