LCT （link cut tree）动态树学习

access操作

将该点 建立一条 到根节点的实边 并且将其他边全部变成虚边
我们先找到该结点 将该节点 旋转的树根 将其右子树 置空 再找到他在结构树中的父亲节点 让他的父亲节点的右儿子 变为该节点

lca操作

我们观察acess操作 就是最后做 access的结点

findroot操作

我们可以先进行一次 access操作 将其旋转到根节点
那么只要一直往左走 就是“原树中的根节点”

makeroot操作

我们先 access（x）到根节点 然后反转这条边

splay（x ，y）

将x到y的路径变成一条实边路径
将x变到根 然后再access y一次

link操作

把x变为根节点 如果 x不是y的节点 那么就改变y的fa节点

cut操作

这个其实 代码中有解释

isroot操作

如果他既不是他父亲节点的左儿子也不是他父亲节点

具体细节在代码里有注释

#include 
/*#include 
#include 
#include 
#include */
using namespace  std;
//#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1ll<<62
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int n, m , k;

struct node {
	int s[2], fa, v;
	int sum, rev;
#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
} tr[N];
void pushrev(int x) {
	swap(ls(x), rs(x));
	tr[x].rev ^= 1;
}

void pushup(int x) {
	tr[x].sum = tr[ls(x)].sum ^ tr[x].v ^ tr[rs(x)].sum;
}
void pushdown(int x) {
	if(tr[x].rev) {
		pushrev(ls(x));
		pushrev(rs(x));
		tr[x].rev = 0;
	}
}
bool isroot(int x) {
	//判断是不是整颗splay的根节点
	return tr[tr[x].fa].s[0] != x && tr[tr[x].fa].s[1] != x;
}
int stk[N];
int top;
void rotate(int x) {
	int y = tr[x].fa;
	int z = tr[y].fa;
	int k = rs(y) == x;
	if(!isroot(y))tr[z].s[rs(z) == y] = x;
	tr[x].fa = z;
	tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].fa = y;
	tr[x].s[k ^ 1] = y, tr[y].fa = x;
	//  注意pushup的顺序
	pushup(y);
	pushup(x);
}
void splay(int x) {
	//这里如果使用 STL 会  TLE
	int top = 0, r = x;
	stk[ ++ top] = r;
	while (!isroot(r)) stk[ ++ top] = r = tr[r].fa;
	while (top) pushdown(stk[top -- ]);
	while (!isroot(x)) {
		int y = tr[x].fa, z = tr[y].fa;
		if (!isroot(y))
			if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
			else rotate(y);
		rotate(x);
	}
}
int access(int x) {
	//建立一条从根节点到x节点的 实边  其他边全部变为虚边
	int z = x;
	int y = 0;
	while(x) {
		splay(x);
		tr[x].s[1] = y;
		pushup(x);
		y = x;
		x = tr[x].fa;
	}
	splay(z);
	return y;
}
void makeroot(int x) {
	// 将x变为原树的根节点
	access(x);
	pushrev(x);
}
int findroot(int x) {
	//找到x所在原树的根节点  并将其旋转到splay的根节点 （防止复杂度退化为o（n））
	access(x);
	while(ls(x))pushdown(x), x = ls(x);
	splay(x);
	return x;
}
void split(int x, int y) {
	//给x到y之间建立一个splay 根节点变为y
	makeroot(x);
	access(y);
}
void link(int x, int y) {
	//如果x和y不连通  将x并到y上
	makeroot(x);
	if(findroot(y) != x)tr[x].fa = y;
}

void cut(int x, int y) {
	//如果x和y之间存在边 则删除该边
	//将x变为树根 然后 查看y是不是x的后继
	makeroot(x);
	if(findroot(y) == x && tr[y].fa == x && !tr[y].s[0]) {
		tr[x].s[1] = tr[y].fa = 0;
		pushup(x);
	}
}

int lca(int root, int x, int y) {
	//  求以root为根的情况下x和y的lca
	makeroot(x);
	access(x);
	return access(y);
}

void solve() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> tr[i].v;
	fer(i, 1, m) {
		int op, x, y;
		cin >> op >> x >> y;
		if(!op) {
			split(x, y);
			cout << tr[y].sum << endl;
		} else if(op == 1)link(x, y);
		else if(op == 2) cut(x, y);
		else {
			splay(x);
			tr[x].v = y;
			pushup(x);
		}
	}
}
int main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
	return 0;
}


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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162