Hello!↵
↵
Recently I have been trying to learn link cut trees (and splay trees, for that matter). I have tried to polish an implementation that is short (for our ICPC notebooks), and also easy to use and extend. I might be extending this blog post towards a tutorial on how link cut trees are used and, more so, how this template can be used.↵
↵
The implementation is here:↵
↵
```↵
struct LinkCut {↵
struct Node {↵
int p = 0, c[2] = {0, 0}, pp = 0;↵
bool flip = 0;↵
int val = 0, dp = 0;↵
};↵
vector<Node> T;↵
↵
LinkCut(int n) : T(n + 1) {}↵
↵
// SPLAY TREE OPERATIONS START↵
↵
int dir(int x, int y) { return T[x].c[1] == y; }↵
↵
void set(int x, int d, int y) {↵
if (x) T[x].c[d] = y, pull(x);↵
if (y) T[y].p = x;↵
}↵
↵
void pull(int x) {↵
if (!x) return;↵
int &l = T[x].c[0], &r = T[x].c[1];↵
T[x].dp = max({T[x].val, T[l].dp, T[r].dp});↵
}↵
↵
void push(int x) {↵
if (!x || !T[x].flip) return;↵
int &l = T[x].c[0], &r = T[x].c[1];↵
swap(l, r); T[l].flip ^= 1; T[r].flip ^= 1;↵
T[x].flip = 0;↵
}↵
↵
void rotate(int x, int d) { ↵
int y = T[x].p, z = T[y].p, w = T[x].c[d];↵
swap(T[x].pp, T[y].pp);↵
set(y, !d, w);↵
set(x, d, y);↵
set(z, dir(z, y), x);↵
}↵
↵
void splay(int x) { ↵
for (push(x); T[x].p;) {↵
int y = T[x].p, z = T[y].p;↵
push(z); push(y); push(x);↵
int dx = dir(y, x), dy = dir(z, y);↵
if (!z) ↵
rotate(x, !dx); ↵
else if (dx == dy) ↵
rotate(y, !dx), rotate(x, !dx); ↵
else↵
rotate(x, dy), rotate(x, dx);↵
}↵
}↵
↵
// SPLAY TREE OPERATIONS END↵
↵
void MakeRoot(int u) {↵
Access(u);↵
int l = T[u].c[0];↵
T[l].flip ^= 1;↵
swap(T[l].p, T[l].pp);↵
set(u, 0, 0);↵
}↵
↵
void Access(int _u) {↵
for (int v = 0, u = _u; u; u = T[v = u].pp) {↵
splay(u); splay(v);↵
int r = T[u].c[1];↵
T[v].pp = 0;↵
swap(T[r].p, T[r].pp);↵
set(u, 1, v);↵
}↵
splay(_u);↵
}↵
↵
void Link(int u, int v) { ↵
assert(!Connected(u, v));↵
MakeRoot(v);↵
T[v].pp = u;↵
}↵
↵
void Cut(int u, int v) {↵
MakeRoot(u); Access(u); splay(v);↵
assert(T[v].pp == u);↵
T[v].pp = 0;↵
}↵
↵
bool Connected(int u, int v) {↵
if (u == v) return true;↵
MakeRoot(u); Access(v); splay(u);↵
return T[v].p == u || T[T[v].p].p == u;↵
}↵
↵
int GetPath(int u, int v) {↵
MakeRoot(u); Access(v); return v;↵
}↵
};↵
```↵
↵
It is around 100 lines long (which is not ideal), but it has some neat features. For example, if you call `lc.GetPath(a, b)`, the implementation will return the root of a splay tree node which contains the whole path from `a` to `b`. Also, the function `lc.Access(v)` will make sure that node `v`'s splay tree would contain the whole path from the root at that time to `v`. ↵
↵
I feel like there is no implementation with a very clean way of modifying it (for the people who don't know LCT), so I decided to adapt one myself (also, I don't like using raw pointers -- if you're like me, you might enjoy this implementation). Also, another thing that I like about this implementation is that the splay tree code is independent to the fact that it's used inside a link-cut tree (it's just plain splay tree code, which can be extracted away).↵
↵
In order to adapt the implementation to path aggregates (updates/queries of any type), you would have to create some function that updates/queries the splay tree node `GetPath(u, v)` and to potentially modify the `push` and `pull` methods (`push` is lazy propagation, whereas `pull` is regular tree update from children).↵
↵
The only thing I'm not happy about is that the `Access` method is pretty ugly. However, I don't want to change its behaviour (I feel it's useful to have `v` splayed after `Access(v)` is called). Please let me know if you can rewrite the code in a more beautiful way.↵
↵
#### [Also, here is a pastebin of a strees test code](https://pastebin.com/UBKL5T0t), in case you want to test the implementation.↵
↵
Any thoughts on how to improve the implementation? What do you think about it overall?
↵
Recently I have been trying to learn link cut trees (and splay trees, for that matter). I have tried to polish an implementation that is short (for our ICPC notebooks), and also easy to use and extend. I might be extending this blog post towards a tutorial on how link cut trees are used and, more so, how this template can be used.↵
↵
The implementation is here:↵
↵
```↵
struct LinkCut {↵
struct Node {↵
int p = 0, c[2] = {0, 0}, pp = 0;↵
bool flip = 0;↵
int val = 0, dp = 0;↵
};↵
vector<Node> T;↵
↵
LinkCut(int n) : T(n + 1) {}↵
↵
// SPLAY TREE OPERATIONS START↵
↵
int dir(int x, int y) { return T[x].c[1] == y; }↵
↵
void set(int x, int d, int y) {↵
if (x) T[x].c[d] = y, pull(x);↵
if (y) T[y].p = x;↵
}↵
↵
void pull(int x) {↵
if (!x) return;↵
int &l = T[x].c[0], &r = T[x].c[1];↵
T[x].dp = max({T[x].val, T[l].dp, T[r].dp});↵
}↵
↵
void push(int x) {↵
if (!x || !T[x].flip) return;↵
int &l = T[x].c[0], &r = T[x].c[1];↵
swap(l, r); T[l].flip ^= 1; T[r].flip ^= 1;↵
T[x].flip = 0;↵
}↵
↵
void rotate(int x, int d) { ↵
int y = T[x].p, z = T[y].p, w = T[x].c[d];↵
swap(T[x].pp, T[y].pp);↵
set(y, !d, w);↵
set(x, d, y);↵
set(z, dir(z, y), x);↵
}↵
↵
void splay(int x) { ↵
for (push(x); T[x].p;) {↵
int y = T[x].p, z = T[y].p;↵
push(z); push(y); push(x);↵
int dx = dir(y, x), dy = dir(z, y);↵
if (!z) ↵
rotate(x, !dx); ↵
else if (dx == dy) ↵
rotate(y, !dx), rotate(x, !dx); ↵
else↵
rotate(x, dy), rotate(x, dx);↵
}↵
}↵
↵
// SPLAY TREE OPERATIONS END↵
↵
void MakeRoot(int u) {↵
Access(u);↵
int l = T[u].c[0];↵
T[l].flip ^= 1;↵
swap(T[l].p, T[l].pp);↵
set(u, 0, 0);↵
}↵
↵
void Access(int _u) {↵
for (int v = 0, u = _u; u; u = T[v = u].pp) {↵
splay(u); splay(v);↵
int r = T[u].c[1];↵
T[v].pp = 0;↵
swap(T[r].p, T[r].pp);↵
set(u, 1, v);↵
}↵
splay(_u);↵
}↵
↵
void Link(int u, int v) { ↵
assert(!Connected(u, v));↵
MakeRoot(v);↵
T[v].pp = u;↵
}↵
↵
void Cut(int u, int v) {↵
MakeRoot(u); Access(u); splay(v);↵
assert(T[v].pp == u);↵
T[v].pp = 0;↵
}↵
↵
bool Connected(int u, int v) {↵
if (u == v) return true;↵
MakeRoot(u); Access(v); splay(u);↵
return T[v].p == u || T[T[v].p].p == u;↵
}↵
↵
int GetPath(int u, int v) {↵
MakeRoot(u); Access(v); return v;↵
}↵
};↵
```↵
↵
It is around 100 lines long (which is not ideal), but it has some neat features. For example, if you call `lc.GetPath(a, b)`, the implementation will return the root of a splay tree node which contains the whole path from `a` to `b`. Also, the function `lc.Access(v)` will make sure that node `v`'s splay tree would contain the whole path from the root at that time to `v`. ↵
↵
I feel like there is no implementation with a very clean way of modifying it (for the people who don't know LCT), so I decided to adapt one myself (also, I don't like using raw pointers -- if you're like me, you might enjoy this implementation). Also, another thing that I like about this implementation is that the splay tree code is independent to the fact that it's used inside a link-cut tree (it's just plain splay tree code, which can be extracted away).↵
↵
In order to adapt the implementation to path aggregates (updates/queries of any type), you would have to create some function that updates/queries the splay tree node `GetPath(u, v)` and to potentially modify the `push` and `pull` methods (`push` is lazy propagation, whereas `pull` is regular tree update from children).↵
↵
The only thing I'm not happy about is that the `Access` method is pretty ugly. However, I don't want to change its behaviour (I feel it's useful to have `v` splayed after `Access(v)` is called). Please let me know if you can rewrite the code in a more beautiful way.↵
↵
#### [Also, here is a pastebin of a strees test code](https://pastebin.com/UBKL5T0t), in case you want to test the implementation.↵
↵
Any thoughts on how to improve the implementation? What do you think about it overall?
