LCT学习笔记

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

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

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

基础知识

引入

Link-Cut-Tree，简称LCT

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

实链剖分

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

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

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

性质

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

基本操作

$access(x)$

作用：把 $x$ 到原树根节点的路径上打通，经过的边全部变成实边，使得原树根与 $x$ 在同一Splay中，且 $x$ 是这条路径的一个端点，以维护当前点到原树根的链上的信息

19.3.29UPD

注意：一定是打通，实际上 $x$ 并没有旋到根的位置
实现：重复以下步骤直至 $x$ 与原树的根联通：
1. 把 $x$ 点splay到当前Splay的根
2. 改变虚实儿子：把 $x$ 到父亲的实边变成虚边，把父亲连向自己的边变成实边
3. push_up
4. 跳到父亲

access = splay + change_child + push_up

$make\_root(x)$

作用：把 $x$ 变成原树的根
实现：
1. 先access(x)，由于LCT的性质， $x$ 此时在当前Splay中深度最大，只有左儿子
2. 翻转 $x$ 所在的整棵Splay，相当于翻转了 $x$ 到原树根的路径，使得当前点只有右儿子，变成深度最小，即为根
  
  具体实现时，先splay(x)，然后只需直接打翻转标记
19.5.29UPD

为什么要splay()？

实际上access(x)时，x是没有旋到根的，只是把路径打通。。。

make_root = access + splay + reverse

$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)$

作用：将两个点之间的路径放到一个Splay中，获取这条链上的信息
实现：make_root(x)使得 $x$ 成为原树的根，再access(y)，最后splay(y)

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

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

$link(x, y)$

作用：连的边（这里默认把 $y$ 连到 $x$ 上）
实现：make_root(x)后，先判断find_root(y)是否等于 $x$ ，如果是则说明已经相连，否则从 $x$ 向 $y$ 连一条轻边。

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

$cut(x, y)$

作用：断开的边（这里默认把 $y$ 与父亲 $x$ 的边断掉）
实现：判断 $x$ 和 $y$ 之间是否真的存在一条边；若存在，直接切断

这里实现上有点复杂，解释一下这个代码吧
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);
}
因为如果 $x$ 和 $y$ 在同一个联通块中，那么纵使在find_root(y)的开始把 $y$ splay到根，最后又把 $x$ 旋回到根了。所以在执行完find_root(y)==x这条语句后当前Splay的根仍然是 $x$

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

注意点

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

LCT中make_root是一个重要的操作，除了access之外的所有操作都建立在make_root之上

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

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

应用

模拟

用来模拟题目中类似的过程，往往在里面再套上一个数据结构来维护一些信息

维护联通性

直接按照题目link与cut

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

维护链上信息

要修改原树中 $u$ 到 $v$ 的路径上的信息

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

维护生成树

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

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

原点——新点——原点

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

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

维护边双

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

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

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

这个操作用DSU实现就好

维护子树信息（只能维护，无法修改）

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

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

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

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

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

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

相对于原来的LCT，发生改变的操作有push_up，access，link

变化的原因：

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

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

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

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

模板(Luogu P3690)

#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;
}