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, in case you want to test the implementation.

Any thoughts on how to improve the implementation? What do you think about it overall?