Link Cut Tree implementation
Difference between en1 and en2, changed 134 character(s)
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? 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English bicsi 2020-12-21 12:56:13 2675
en3 English bicsi 2020-04-11 23:38:39 14 Tiny change: 'tebin.com/UBKL5T0t), in case' -> 'tebin.com/BhdfucH6), in case'
en2 English bicsi 2020-04-11 23:37:37 134 Tiny change: 'l way.\n\n[Also, her' -> 'l way.\n\n#### [Also, her'
en1 English bicsi 2020-04-11 23:35:48 4025 Initial revision (published)