LCT学习笔记

动态维护树上一些问题的数据结构,前置技能需要Splay

这个东西好像全世界都会了,就我没写过

本文大多数内容都是整理自网上各种博客和hyj的课件

基础知识

引入

Link-Cut-Tree,简称LCT

学完树链剖分后,我们发现很多树上操作问题都可以用树剖解决。可是如果树的形态不断改变,即需要支持加边、删边操作,就需要用到LCT

实链剖分

类似于轻重链剖分,对于每个点将其与某个儿子的边划为实边,其余的划为虚边

实链剖分中虚实儿子会不断改变,因此我们用Splay来维护,每条实链对应一个Splay

所以其实LCT的本质就是利用树剖的思想,把整棵树拆成一条条实链,通过Splay维护实链,从而动态维护树上信息

性质

  • 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径, 其内部是以深度为关键字排序
  • 每个节点包含且仅包含于一个Splay
  • 每个节点与它实边相连的点在同一个Splay中,实边包含在Splay当中;虚边总是由一棵Splay中的根连向另一棵Splay中最深的节点。连向的节点记录父亲,连出的节点不记录儿子(认父不认子)

基本操作

access(x)access(x)

  • 作用:把xx到原树根节点的路径上打通,经过的边全部变成实边,使得原树根与xx在同一Splay中,且xx是这条路径的一个端点,以维护当前点到原树根的链上的信息
  • 实现:重复以下步骤直至xx与原树的根联通:
    1. xxsplay到当前Splay的根
    2. 改变虚实儿子:把xx到父亲的实边变成虚边,把父亲连向自己的边变成实边
    3. push_up
    4. 跳到父亲

access = splay + change_child + push_up

make_root(x)make\_root(x)

  • 作用:把xx变成原树的根

  • 实现:

    1. access(x),由于LCT的性质,xx此时在当前Splay中深度最大,只有左儿子

    2. 翻转xx所在的整棵Splay,相当于翻转了xx到原树根的路径,使得当前点只有右儿子,变成深度最小,即为根

      具体实现时,先splay(x),然后只需直接打翻转标记

make_root = access + splay + reverse

find_root(x)find\_root(x)

  • 作用:找一个点所在原树的根
  • 实现:access(x)splay(x)后,当前Splay最左边的点即为原树的根,最后再splay一下保证复杂度
  • 注意:
    1. find_root的常数比较大,如果只有加边没有删边操作的话,可以用DSU代替此操作
    2. 在往左走的时候一定要记得push_down,且一开始就要push_down一下

find_root = access + splay + go_left_child + splay

split(x,y)split(x,y)

  • 作用:将两个点之间的路径放到一个Splay中,获取这条链上的信息

  • 实现:make_root(x)使得xx成为原树的根,再access(y),最后splay(y)

    最后splay(y)是用来更新信息的,同时保证Splay的复杂度

split(x, y) = make_root(x) + access(y) + splay(y)

  • 作用:连的边(这里默认把yy连到xx上)
  • 实现:make_root(x)后,先判断find_root(y)是否等于xx,如果是则说明已经相连,否则从yyxx连一条轻边。

link(x, y) = make_root(x) + (fa[y] = x)

cut(x,y)cut(x, y)

  • 作用:断开的边(这里默认把yy与父亲xx的边断掉)

  • 实现:判断xxyy之间是否真的存在一条边;若存在,直接切断

    这里实现上有点复杂,解释一下这个代码吧

    1
    2
    3
    4
    5
    6
    make_root(x);
    if (find_root(y) == x && Tree[y].fa == x && !ls(y))
    {
    Tree[y].fa = rs(x) = 0;
    push_up(x);
    }

    因为如果xxyy在同一个联通块中,那么纵使在find_root(y)的开始把yysplay到根,最后又把xx旋回到根了。所以在执行完find_root(y)==x这条语句后当前Splay的根仍然是xx

cut(x, y) = make_root(x) + (f[y] = right_child[x] = 0)

注意点

  1. LCT中的Splay和普通Splay的区别:
    • rotate时要判断if(!is_root(f)),因为有可能ff已经为当前Splay的根,如果不判断的话就会把它向父亲的虚边变实,而这并不是我们所期望的
    • splay中循环条件由while(Tree[x].fa != y)变成了while(!is_root(x)
    • splay中需要先从根push_down到当前点,再rotate
  2. push_down一般写法与线段树的有点区别:当前点如果有翻转标记的话,它的左右儿子是还没有被翻转的,在标记下传的同时进行翻转。因此在find_root往左儿子走之前就要push_down一下。其实也就是每访问一个点之前就要push_down

至此,LCT的基本操作就学习口胡完啦

我是不会告诉你我到现在还没有开始码的

功能

维护联通性

直接按照题目linkcut

查询两点连通性:find_root,如果没有cut的话可以直接用DSU

维护链上信息

要修改原树中uuvv的路径上的信息

直接split(u,v),然后在Splay中操作,利用push_down的lazy标记完成所有点的改变

维护生成树

维护一个图的最小或最大生成树

因为LCT无法维护边权,所以考虑化边为点。原图中一条边的连接,在新图中变为两条边,即:

原点——新点——原点

原点不带权,新点带权,其权值为原来的边权

LCT维护一下链上最大值和次大值,每次直接连边,或是split更新答案

维护边双

加边的时候,如果这两个点已经联通,那么这条边加入后就一定会形成一个环,因此这个环里的所有点就处在同一个边双里

用类似缩点的方法,遇到环,则新建一个点代表这个边双,把这个环里的所有点的父亲指向新点

凡要用到一个点就x = fa[x],相当于踏入这个环就踏进这个新点

这个操作用DSU实现就好

维护子树信息(只能维护,无法修改)

我们发现,在LCT中都是维护的链上信息,那么如何维护原树子树信息呢?

不难发现,原树子树信息 = 虚子树 + 实子树 + 自身信息

于是相当于需要多维护一个虚子树信息

对于每个父亲与自己不在同一Splay中的点,把自己的信息加入到自己存的父亲的虚儿子信息库

如果维护信息是可减的,一个数组存,更新是 O(1)O(1)

如果维护信息不可减(如min,max),就需要堆或者其它数据结构维护,复杂度多一个log\log

相对于原来的LCT,发生改变的操作有push_upaccesslink

变化的原因:

  • push_up:要多维护虚子树的信息
  • access:在改变虚边实边时,xx的虚子树信息会变化,所以要修改
  • link:在把xxyy虚边的时候,yy的虚子树信息会变化,同时因为每个点的子树信息要算上虚子树信息,所以所有yy祖先的子树信息都会变化,需要暴力把所有祖先修改,很麻烦。但是我们可以先直接make_root(y),这样yy就没有祖先了

可以发现,需要修改的地方都是虚边改变了的地方,根本原因是push_up时只维护了总子树信息,并没有维护虚儿子信息。所以需要手动修改


至此,LCT的基本功能又学习口胡完啦

我是不会告诉你我到现在还是没有开始码的

模板(Luogu P3690)

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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

template <typename T> T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

const int Maxn = 3e5 + 100;

int N, M;

namespace LCT
{
#define ls (Tree[x].ch[0])
#define rs (Tree[x].ch[1])
struct tree
{
int ch[2], fa, rev, sum, val;
}Tree[Maxn];
int Stack[Maxn], top;

inline int is_root (int x) { return (Tree[Tree[x].fa].ch[0] != x) && (Tree[Tree[x].fa].ch[1] != x); }

inline int judge_dir (int x) { return x == Tree[Tree[x].fa].ch[1]; }

inline void push_up (int x) { Tree[x].sum = Tree[ls].sum ^ Tree[rs].sum ^ Tree[x].val; }

inline void push_down (int x) { if (Tree[x].rev) swap(ls, rs), Tree[ls].rev ^= 1, Tree[rs].rev ^= 1, Tree[x].rev = 0; }

inline void connect (int x, int f, int dir) { Tree[x].fa = f, Tree[f].ch[dir] = x; }

inline void rotate (int x)
{
/**/ int f = Tree[x].fa, anc = Tree[f].fa, dirx = judge_dir(x), dirf = judge_dir(f);
Tree[x].fa = anc; if (!is_root(f)) Tree[anc].ch[dirf] = x;
connect (Tree[x].ch[dirx ^ 1], f, dirx);
connect (f, x, dirx ^ 1);
push_up(f), push_up (x);
}

inline void splay (int x)
{
Stack[++top] = x; for (int y = x; !is_root(y); y = Tree[y].fa) Stack[++top] = Tree[y].fa;
while (top) push_down (Stack[top--]);
for (; !is_root(x); rotate(x)) if (!is_root(Tree[x].fa)) rotate (judge_dir(x) == judge_dir(Tree[x].fa) ? Tree[x].fa : x);
}

/**/inline void access (int x) { for (int y = 0; x; y = x, x = Tree[x].fa) splay (x), rs = y, push_up (x); }

inline void make_root (int x) { access (x), splay (x), Tree[x].rev ^= 1; }

inline int find_root (int x) { access (x), splay (x); push_down (x); while (ls) x = ls, push_down (x); splay (x); return x; }
inline void split (int x, int y) { make_root (x), access (y), splay (y); }

/**/inline void link (int x, int y) { make_root (x); if (find_root (y) == x) return ; Tree[x].fa = y; }

inline void cut (int x, int y) { make_root (x); if (find_root (y) == x && Tree[y].fa == x && !Tree[y].ch[0]) Tree[y].fa = rs = 0, push_up (x); }

inline int query (int x, int y) { split (x, y); return Tree[y].sum; }

inline void modify (int x, int y) { access (x), splay(x); Tree[x].val = y; push_up(x); }
}

inline void Solve ()
{
while (M--)
{
int op = read<int>(), x = read<int>(), y = read<int>();
if (!op) printf("%d\n", LCT :: query (x, y));
if (op == 1) LCT :: link (x, y);
if (op == 2) LCT :: cut (x, y);
if (op == 3) LCT :: modify (x, y);
}
}

inline void Input ()
{
N = read<int>(), M = read<int>();
for (int i = 1; i <= N; ++i) LCT :: Tree[i].val = read<int>();
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif
Input();
Solve();
return 0;
}
感谢你的赞赏!