概念辨析
- 辅助树
- 轻边和重边
操作介绍
- access
- make_root
- find_root
- split
- link
- cut
细节问题
代码

前言:这个算法似乎机房全都会,就我不会了TAT...强行搞了很久,勉强照着别人代码抄了一遍qwq

这个本人看论文实在看不懂,太菜了啊!!! 只好直接看如何实现...可是实现也看不太懂...

但直到我看到一篇大佬博客!!! point here 是真的讲的好,一点都不敷衍.真没收钱

本篇比较干货qwq(没图啊!!!) 一定要耐住性子学算法!!!

概念辨析

但在之前还是要辨析几个概念:

辅助树

本人理解就是对于原树抽象出一个splay 或者说很多棵splay (啥,你告诉我原树是多叉树,splay只是一个二叉树)

其实就是将一个splay划分成很多部分(每一部分维护原图中的一条链) 然后对于这些部分连轻边.

(建议先认真看看那些基础概念) 然后对于一条链来说,深度两两不同,我们就可以用这个作为splay的键值来排序

然后这就可以维护出原树了... 为什么呢? 因为虽然父亲只能有两个儿子,但是有很多儿子来认他啊qwq

(就像造树的时候只要给每个点一个fa就行了) 然后每条链又在splay中可以确定他们的先后顺序(也就是深度大小)

轻边和重边

这个不像树剖,这个就是随便给的(根据操作access来改变) 然后重边存在于splay中的子认父也认 的边, 也就是维护链时候的边. 然后轻边,就是只连到父亲时子认父不认 的边,就是一颗splay连到重链顶端父亲的那条边,而且一个点只能有一个重边!

操作介绍

然后就直接介绍操作吧(你还是没听懂?那看看别人博客的概念介绍吧qwq)

access

就是拉链,就是把一个点到根节点路径全都变为重边,且它是这条路径的一个端点.

如何实现呢qwq... 就是每次把当前这个节点splay到根,然后这个splay的父亲认了他这个儿子就行了,

接下来上传信息... 不断操作,直到到根 (注意要把他变为树的一个端点,所以要一开始要将它的儿子认为空的)

access=splay+child+push_up

make_root

使得一个点变为原树的根,然后这就可以便于维护路径信息了.

首先先把这个点access到根,之后将这个点splay到当前splay的根,然后再下放一个rev的标记就行了.

这是因为你使当前重链的深度完全翻转了(注意,我们splay是按照深度排序的!!!)

x就变为深度最小的点(即根节点)

make_root=access+splay+rev

find_root

找到原树的根,这个就易于判断连通性了(类似于并查集)

又是access到根,然后也是splay到根. (这样似乎很好维护一些东西,而且更方便去想了)

然后直接一直向左边走,最下面那个就是根节点了(深度最小, 时间复杂度因为有双旋所以可以保证)

而且在走左子树的时候要push_down!! (大佬博客上讲的,我还没被坑过qwq)

find_root=access+splay+go_left_child

split

将原图中的一条路径变为一条以它们为端点的重链.

假设我们split(x,y). 首先先把make_root(x)便于操作. 然后access(y),拉一条路径出来.

为了查找信息我们splay(y)到splay的根上去,直接访问y的信息(中间splay有push_up)

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

link

将原图中的两个点连一条边

我们把link(x,y)定义为把x的父亲认做y. (其实你互换也是可以的)

如果操作合法,我们只要make_root(x)然后x的父亲认做y就行了.

就是让x变为他所在树的根就行了qwq.. 不合法的话,就判断联通性就行了.

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

cut

将原图中的一条边断掉

我们同样把cut(x,y)定义为把原图中x与其父亲y的边断掉. (同上互换也是可以的)

这个合法的话,直接把他们中的那条链split出来,直接断掉就行了...

不合法的话,同样尝试split出来,如果x的左儿子不是y就不行.

这样意义就是y在原树中不是x的父亲,不能cut掉.

cut(x,y)=split(x,y)+left_child[y]=fa[x]=0

至此link_cut_tree所有基础知识已经讲完qwq...然后高端操作只能自己做题了...

细节问题

这个lct细节是真的多,一不小心就调不出来了啊!!!

rotate和普通的不同,要判断是不是当前splay的根!!!!

而且连边的时候一定要注意顺序啊!!!

就是判断is_root(u)之前不能连u-v的那条边!!!!

splay那里也是判断is_root的时候要注意对象啊,是fa[u]!!!
make_root那里不能先交换一遍!!!直接打标记在那里就行了!!!

(有些人写法是先交换,再打左右儿子标记,我代码不同啊!!!)

splay中t要从o开始,然后判断!is_root(t)而不能从fa[o]开始,这是因为fa[o]可能为\(0\)啊!!!
rotate中是push_up而不是push_down,前面splay中push_down完了啊!!!

代码

(没有注释....凑合对对,这道题是luogu模板)

#include <bits/stdc++.h>

#define debug cerr << "Pass" << endl

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}

inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {

	int x = 0, fh = 1; char ch = getchar();

	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;

	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

	return x * fh;

}

void File() {

#ifdef zjp_shadow

	freopen ("P3690.in", "r", stdin);

	freopen ("P3690.out", "w", stdout);

#endif

}

const int maxn = 1e6 + 1e3;

int val[maxn];

#define ls(u) ch[u][0]

#define rs(u) ch[u][1]

struct Link_Cut_Tree {

	int fa[maxn], ch[maxn][2], rev[maxn], xsum[maxn];

	inline bool is_root(int o) { return o != ls(fa[o]) && o != rs(fa[o]); }

	inline bool get(int o) { return o == rs(fa[o]); }

	inline void push_up(int o) { xsum[o] = xsum[ls(o)] ^ xsum[rs(o)] ^ val[o]; }

	inline void push_down(int o) {

		if (rev[o]) { swap(ls(o), rs(o)); rev[ls(o)] ^= 1; rev[rs(o)] ^= 1; rev[o] = 0; }

	}

	inline void rotate(int v) {

		int u = fa[v], t = fa[u], d = get(v);

		fa[ch[u][d] = ch[v][d ^ 1]] = u;

		fa[v] = t; if (!is_root(u)) ch[t][rs(t) == u] = v;

		fa[ch[v][d ^ 1] = u] = v;

		push_up(u); push_up(v);

	}

	int sta[maxn], top;

	inline void splay(int u) {

		sta[top = 1] = u;

		for (register int t = u; !is_root(t); t = fa[t]) sta[++ top] = fa[t];

		while (top) push_down(sta[top --]);

		for (; !is_root(u); rotate(u)) if (!is_root(fa[u])) rotate(get(u) ^ get(fa[u]) ? u : fa[u]);

	}

	inline void access(int o) { for (int t = 0; o; o = fa[t = o]) splay(o), rs(o) = t, push_up(o); }

	inline void make_root(int o) { access(o); splay(o); rev[o] ^= 1; }

	inline int find_root(int o) { access(o); splay(o); while (ls(o)) o = ls(o), push_down(o); splay(o); return o; }

	inline void split(int v, int u) { make_root(v); access(u); splay(u); }

	inline bool link(int v, int u) { make_root(v); if (find_root(u) == v) return false; fa[v] = u; return true; }

	inline void cut(int v, int u) { split(v, u); if (ls(u) == v) ls(u) = fa[v] = 0; }

} lct;

int n, m;

int main () {

	File();

	n = read(); m = read();

	For (i, 1, n) val[i] = lct.xsum[i] = read();

	For (i, 1, m) {

		int opt = read(), x = read(), y = read();

		if (!opt) { lct.split(x, y); printf ("%d\n", lct.xsum[y]); }

		else if (opt == 1) lct.link(x, y);

		else if (opt == 2) lct.cut(x, y);

		else { lct.access(x); lct.splay(x); val[x] = y; lct.push_up(x); }

	}

	return 0;

}

巴特西

link-cut-tree 简单介绍