Skip to content

Link Cut Tree

Overview

A Link/Cut Tree is a data structure for solving dynamic tree problems.

It is also written Link-Cut Tree and abbreviated LCT. It is not called a "dynamic tree", though: that name refers to a class of problems.

The LCT is built on the splay tree, but the splay trees inside an LCT differ from ordinary ones in a few details (they are extended slightly).

Motivating problem

Maintain a tree under the following operations:

  • Update the weights on the path between two nodes.
  • Query the sum of the weights on the path between two nodes.
  • Update the weights in the subtree of a node.
  • Query the sum of the weights in the subtree of a node.

This is a template problem for heavy-light decomposition.

Now add one more operation:

  • Cut some edges and add others, such that the result is still a tree.

The answers above must be computed online.

This is now a dynamic tree problem, and an LCT solves it.

Dynamic tree problems

Maintain a forest under edge deletions and edge insertions, where the graph is guaranteed to remain a forest after each of them. We want to maintain some information about this forest.

Typical operations are: test whether two nodes are connected, find the sum of the weights on the path between two nodes, link two nodes, cut an edge, and update the stored information.

Heavy-light decomposition from the LCT's point of view

  • Decompose the whole tree by subtree size and relabel the nodes.
  • After relabeling, each path of the decomposition occupies a contiguous range of labels, so a segment tree can perform range operations on it.

Moving on to dynamic tree problems

Heavy-light decomposition, as just described, partitions the tree by subtree size. Can we define a different decomposition, one better suited to dynamic tree problems?

Think about what kind of paths a dynamic tree problem needs.

The forest changes over time, so we want the paths to be ones we pick ourselves, in whatever way helps us answer the queries.

Preferred-path decomposition

Among the edges from a node to its children, we pick one ourselves. The edge we pick is a preferred edge, and the others are virtual edges. The child at the other end of a preferred edge is the preferred child. A path made of preferred edges is likewise called a preferred path. Keep in mind the main reason for choosing this decomposition: the paths are ours to choose, so they are flexible and can change. It is because of this flexibility that we maintain the preferred paths with splay trees.

LCT

Put simply, an LCT uses a set of splay trees to maintain a dynamic tree path decomposition, so that range operations can be performed on a tree that keeps changing. For each preferred path, we build one splay tree that maintains the information of the whole path as a range.

Auxiliary tree

We first list some properties of the auxiliary tree, and then look at a figure to see how it is actually laid out.

In this article, you can think of it this way: several splay trees make up an auxiliary tree, and each auxiliary tree maintains one tree; several auxiliary trees make up the LCT, which maintains the whole forest.

  1. An auxiliary tree consists of several splay trees. Each splay tree maintains one path of the original tree, and its inorder traversal lists the nodes of that path from top to bottom.
  2. The nodes of the original tree correspond one-to-one to the splay nodes of the auxiliary tree.
  3. The splay trees of an auxiliary tree are not independent of one another. The root of a splay tree would normally have no parent, but in an LCT its parent pointer points to the parent of this path in the original tree (that is, the parent of the topmost node of the path). Unlike an ordinary parent link in a splay tree, this one goes one way: the child knows its parent, but the parent does not know the child. It corresponds to a virtual edge of the original tree. Consequently, each connected component has exactly one node whose parent is null.
  4. Because of these properties, no operation ever needs the original tree: it can always be recovered uniquely from the auxiliary tree. So the auxiliary tree is all we maintain.

Suppose the original tree is the one in the figure. (Thick edges are preferred edges, dashed edges are virtual edges.)

tree

By the definitions above, its auxiliary tree looks like this.

auxtree

  • A preferred path of the original tree: its nodes all lie in one splay tree of the auxiliary tree.
  • A virtual path of the original tree: in the auxiliary tree, the splay tree containing the child has its Father pointing to the parent, but neither child pointer of the parent points to the child.
  • Note: the root of the original tree is not the same as the root of the auxiliary tree.
  • The Father pointers of the original tree are not the same as those of the auxiliary tree.
  • The auxiliary tree can be rerooted freely, as long as the properties of the auxiliary tree and of splay trees are preserved.
  • Switching paths between virtual and preferred is easy on the auxiliary tree, and that is exactly how the tree path decomposition is maintained dynamically.

Variables used below

  • ch[N][2]: left and right children
  • f[N]: parent pointer
  • sum[N]: sum of the weights on the path
  • val[N]: vertex weight
  • tag[N]: reversal tag
  • laz[N]: lazy tag on the weights
  • siz[N]: subtree size in the auxiliary tree
  • Other_Vars

Function declarations

General data structure functions (the names say it all)

  1. PushUp(x)
  2. PushDown(x)

Splay tree functions

These functions come from the splay tree; see the splay tree page for details.

  1. Get(x): tells which child of its parent \(x\) is.
  2. Splay(x): working together with Rotate, rotates \(x\) up to the root of its current splay tree.
  3. Rotate(x): rotates \(x\) up one level.

New operations

  1. Access(x): puts all nodes from the root to \(x\) on one preferred path, so that the path from the root to \(x\) is a preferred path and is stored in a single splay tree. This is the only operation you must implement; implement the others as the problem requires.
  2. IsRoot(x): tests whether \(x\) is the root of the tree it is in.
  3. Update(x): after Access, recursively calls PushDown from top to bottom to update the information.
  4. MakeRoot(x): makes \(x\) the root of its tree.
  5. Link(x, y): adds an edge between \(x\) and \(y\).
  6. Cut(x, y): deletes the edge between \(x\) and \(y\).
  7. Find(x): finds the index of the root of the tree containing \(x\).
  8. Fix(x, v): sets the vertex weight of \(x\) to \(v\).
  9. Split(x, y): extracts the path between \(x\) and \(y\), ready for range operations.

Macro definitions

  • #define ls ch[p][0]
  • #define rs ch[p][1]

The functions in detail

PushUp()

1
2
3
4
void PushUp(int p) {
  // maintain other variables
  siz[p] = siz[ls] + siz[rs] + 1;
}

PushDown()

1
2
3
4
5
6
void PushDown(int p) {
  if (tag[p] != std_tag) {
    // pushdown the tag
    tag[p] = std_tag;
  }
}

Splay() && Rotate()

Here Splay() and Rotate() differ slightly from their splay tree versions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#define Get(x) (ch[f[x]][1] == x)

void Rotate(int x) {
  int y = f[x], z = f[y], k = Get(x);
  if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
  // The line above must come first. An ordinary splay tree does not need this; the reason is isRoot (explained below)
  ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
  ch[x][!k] = y, f[y] = x, f[x] = z;
  PushUp(y), PushUp(x);
}

void Splay(int x) {
  Update(
      x);  // Defined just below. Before splaying, PushDown every node on the path the rotations will pass through
  for (int fa; fa = f[x], !isRoot(x); Rotate(x)) {
    if (!isRoot(fa)) Rotate(Get(fa) == Get(x) ? fa : x);
  }
}

The functions above are covered on the splay tree page.

The functions below are specific to the LCT.

isRoot()

1
2
3
// As said earlier, in an LCT a parent cannot find a child that is not its preferred child,
// so a node that is neither the left nor the right child of its parent is the root of its current splay tree
#define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)

Access()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Access is the core operation of an LCT.
// Suppose we want the answer for a path, and that path is exactly one of our current splay trees:
// then we just read the information off it. Look at the code first, then follow the procedure in the figures
int Access(int x) {
  int p;
  for (p = 0; x; p = x, x = f[x]) {
    Splay(x), ch[x][1] = p, PushUp(x);
  }
  return p;
}
  • Take this tree, where solid lines are preferred edges and dashed lines are virtual edges.

    initial tree

  • Its auxiliary tree might look like this (a different construction may give a different LCT structure).

    initial auxtree

  • Now we call Access(N): every edge on the path from \(A\) to \(N\) becomes a preferred edge, and the path is pulled into a single splay tree.

    access tree

  • To do this, we update the splay trees step by step, from the bottom up.

  • First, rotate \(N\) to the root of its current splay tree.

  • To preserve the properties of the auxiliary tree (AuxTree), the preferred edge from \(N\) to \(O\) must become a virtual edge.

  • Since a child may point to a parent that does not point back, we can simply set the child pointer of \(N\) to NULL and leave the other side untouched.

  • The AuxTree thus changes from the figure below into the one after it.

    step 1 auxtree

  • Next, rotate \(I\), the Father that \(N\) points to, to the root of its own splay tree.

  • The preferred edge \(I\)–\(K\) has to go, so we point the right child of \(I\) at \(N\), which gives a splay tree for \(I\)–\(L\).

    step 2 auxtree

  • We repeat the same steps. The Father of \(I\) points to \(H\), so we rotate \(H\) to the root of its splay tree and set the rs of \(H\) to \(I\).

  • The tree now looks like this.

    step 3 auxtree

  • In the same way, we call Splay(A) and point the right child of \(A\) at \(H\).

  • This gives the following AuxTree, in which the whole path \(A\)–\(N\) lies in a single splay tree.

    step final auxtree

1
2
3
4
5
6
7
8
// The code once more
int Access(int x) {
  int p;
  for (p = 0; x; p = x, x = f[x]) {
    Splay(x), ch[x][1] = p, PushUp(x);
  }
  return p;
}

As you can see, Access() is quite simple. It has only four steps:

  1. Rotate the current node to the root.
  2. Replace its right child with the previous node.
  3. Update the information of the current node.
  4. Move to the parent of the current node and repeat.

The Access given here also returns a value: the parent endpoint of the virtual edge in the last switch between virtual and preferred paths. This value means two things:

  • When Access is called twice in a row, the value returned by the second call is the LCA of the two nodes.
  • It is the root of the splay tree that holds the path from \(x\) to the root. This node has already been rotated to the root, and its parent is null.

Update()

1
2
3
4
5
// pushDown level by level, from top to bottom
void Update(int p) {
  if (!isRoot(p)) Update(f[p]);
  pushDown(p);
}

makeRoot()

  • Make_Root() is every bit as important as Access(). When we maintain path information, we are bound to meet paths whose depth does not increase strictly, and by the properties of the AuxTree such a path cannot be stored in a single splay tree.
  • This is where Make_Root() comes in.
  • Make_Root() makes a given node the root of the original tree. How can this be implemented?
  • Let \(y\) be the value returned by Access(x). At this point the path from \(x\) to the current root forms exactly one splay tree, and its root is \(y\).
  • Represent the tree as a directed graph by orienting every edge from child to parent. Rerooting then amounts to reversing every edge on the path from \(x\) to the root (think this through carefully).
  • So it suffices to reverse the path from \(x\) to the current root.
  • Since \(y\) is the root of the splay tree that represents this path, we apply a range reversal to the splay tree rooted at \(y\).
1
2
3
4
5
void makeRoot(int p) {
  p = Access(p);
  swap(ch[p][0], ch[p][1]);
  tag[p] ^= 1;
}
  • Linking two nodes is easy: call Make_Root(x), then set the parent of \(x\) to \(y\). Obviously, this must never be done to two nodes of the same tree, so remember to check first.
1
2
3
4
5
void Link(int x, int p) {
  makeRoot(x);
  splay(x);
  f[x] = p;
}

Split()

  • Split has a simple meaning: it extracts a splay tree that maintains the path from \(x\) to \(y\).
  • Call MakeRoot(x), then Access(y). If you want \(y\) at the root, also call Splay(y).
  • These three steps of Split bring the required path into the subtree of \(y\), where other operations can then be applied.

Cut()

  • Cut comes in two cases: the cut is guaranteed to be valid, or it is not.
  • If it is guaranteed to be valid, call Split(x, y). Now \(y\) is the root and \(x\) must be its child, so we disconnect them in both directions, like this:
1
void Cut(int x, int p) { makeRoot(x), Access(p), Splay(p), ls = f[x] = 0; }

If validity is not guaranteed, we have to check whether the edge exists. One option is to store the edges in a map, but there is also a way that uses the structure itself:

An edge can be cut only if these three conditions hold:

  1. \(x\) and \(y\) are connected.
  2. There is no other path on the path between \(x\) and \(y\).
  3. \(x\) has no right child.

Taken together, the three conditions say one thing: there is an edge between \(x\) and \(y\).

The implementation is left to you as an exercise. Testing connectivity needs Find, which comes later; for the other two conditions, a little thought about the structure shows how to test them.

Find()

  • Find() finds the root of the original tree containing \(x\); do not confuse the root of the original tree with the root of the auxiliary tree. Call Access(p) and then Splay(p). The root is the node of smallest depth in the tree, so keep going to the left child, calling PushDown along the way.
  • Stop when there is no ls. It is that simple.
  • Note: after every query, Splay the node you found up to the root, or the complexity bound is lost.
1
2
3
4
5
6
7
8
int Find(int p) {
  Access(p);
  Splay(p);
  pushDown(p);
  while (ls) p = ls, pushDown(p);
  Splay(p);
  return p;
}

Caveats

  • Before every operation, think about whether a PushUp or a PushDown is needed. The LCT is so flexible that a single missing PushDown or PushUp can apply an update to nodes it should never touch!
  • Rotate in an LCT differs slightly from the splay tree version: if (z) must come first.
  • Splay in an LCT always rotates to the root. There is no "rotate until it is a child of some node" variant, because none is needed.

Time complexity

Most LCT operations are built on Access, and the rest take constant time, so we only need to analyze Access.

The cost of Access comes mainly from its repeated splay operations and from traversing the virtual edges on the path. We analyze the two parts separately.

  1. splay

    • Define \(w(x) = \log size(x)\), where \(size(x)\) is the total number of virtual and preferred edges rooted at \(x\).

    • Define the potential function \(\Phi = \sum_{x \in T} w(x)\), where \(T\) is the set of all nodes.

    By the analysis of the time complexity of splay trees, a splay operation takes \(O(\log n)\) amortized time.

  2. Traversing virtual edges

    Following heavy-light decomposition, define two kinds of virtual edges:

    • Heavy virtual edge: a virtual edge from a node \(v\) to its parent, where \(size(v) > \frac{1}{2} size(parent(v))\).

    • Light virtual edge: a virtual edge from a node \(v\) to its parent, where \(size(v) \leq \frac{1}{2} size(parent(v))\).

    Virtual edges can be handled with the potential method. Define the potential function \(\Phi\) as the number of heavy virtual edges, and the amortized cost as \(c_i = t_i + \Delta \Phi_i\), where \(t_i\) is the actual cost of the operation and \(\Delta \Phi_i\) is the change in potential.

    • Traversing a heavy virtual edge turns it into a preferred edge. This decreases the potential by \(1\), because it improves the structure of the tree by strengthening an important connection. Its actual cost is \(O(1)\), which cancels the increase in potential, so it adds nothing to the amortized cost. All of the amortized cost falls on the light virtual edges.

    • Each Access traverses at most \(O(\log n)\) light virtual edges. It therefore spends at most \(O(\log n)\) in actual cost and creates \(O(\log n)\) heavy virtual edges; that is, the potential grows by \(O(\log n)\).

    So the amortized cost of traversing virtual edges, the sum of the actual cost and the change in potential, is \(O(\log n)\).

To sum up, the cost of Access in an LCT is the cost of the splay operations plus the cost of traversing virtual edges, so its amortized complexity is \(O(\log n)\): on an LCT with n nodes, m Access operations take \(O(n \log n + m \log n)\) time. Operations built on Access, such as Cut, Link and Findroot, therefore also take \(O(\log n)\) amortized time.

Practice problems

Maintaining path information

With Split(x,y), an LCT extracts the path from node \(x\) to node \(y\) into a splay tree rooted at \(y\), so updates and queries on a tree path become operations on a balanced tree. This is what makes the LCT good at maintaining path information. Binary search along a tree path is also a factor of \(O(\log n)\) faster with an LCT than with heavy-light decomposition.

Example: [Chinese national training team] Tree II

You are given a tree with \(n\) nodes; every node initially has weight \(1\). There are \(q\) operations, each of one of the following four kinds:

  1. - u1 v1 u2 v2: delete the edge between \(u_1\) and \(v_1\) and add an edge between \(u_2\) and \(v_2\). The operation is guaranteed to be valid, and the result is still a tree.
  2. + u v c: add \(c\) to the weight of every node on the path between \(u\) and \(v\).
  3. * u v c: multiply the weight of every node on the path between \(u\) and \(v\) by \(c\).
  4. / u v: print the sum of the weights of the nodes on the path between \(u\) and \(v\), modulo \(51061\).

    \(1\le n,q\le 10^5,0\le c\le 10^4\)

    The - operation is simply Cut(u1,v1) followed by Link(u2,v2).

To update the path between \(u\) and \(v\), first call Split(u,v).

This problem needs subtree add, subtree multiply and subtree sum on the auxiliary tree. So besides the subtree reversal tag that every LCT maintains, we also keep a subtree addition tag and a subtree multiplication tag. They are handled exactly as in a splay tree.

When an addition tag is applied or pushed down, the sum of a subtree changes by an amount that depends on the number of nodes in it, so we also maintain the subtree size siz.

Order matters when pushing tags down: push down the multiplication tag first, then the addition tag. The reversal tag does not conflict with the addition and multiplication tags.

Reference code
  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
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
constexpr long long MAXN = 100010;
constexpr long long mod = 51061;
long long n, q, u, v, c;
char op;

struct Splay {
  long long ch[MAXN][2], fa[MAXN], siz[MAXN], val[MAXN], sum[MAXN], rev[MAXN],
      add[MAXN], mul[MAXN];

  void clear(long long x) {
    ch[x][0] = ch[x][1] = fa[x] = siz[x] = val[x] = sum[x] = rev[x] = add[x] =
        0;
    mul[x] = 1;
  }

  long long getch(long long x) { return (ch[fa[x]][1] == x); }

  long long isroot(long long x) {
    clear(0);
    return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
  }

  void maintain(long long x) {
    clear(0);
    siz[x] = (siz[ch[x][0]] + 1 + siz[ch[x][1]]) % mod;
    sum[x] = (sum[ch[x][0]] + val[x] + sum[ch[x][1]]) % mod;
  }

  void pushdown(long long x) {
    clear(0);
    if (mul[x] != 1) {
      if (ch[x][0])
        mul[ch[x][0]] = (mul[x] * mul[ch[x][0]]) % mod,
        val[ch[x][0]] = (val[ch[x][0]] * mul[x]) % mod,
        sum[ch[x][0]] = (sum[ch[x][0]] * mul[x]) % mod,
        add[ch[x][0]] = (add[ch[x][0]] * mul[x]) % mod;
      if (ch[x][1])
        mul[ch[x][1]] = (mul[x] * mul[ch[x][1]]) % mod,
        val[ch[x][1]] = (val[ch[x][1]] * mul[x]) % mod,
        sum[ch[x][1]] = (sum[ch[x][1]] * mul[x]) % mod,
        add[ch[x][1]] = (add[ch[x][1]] * mul[x]) % mod;
      mul[x] = 1;
    }
    if (add[x]) {
      if (ch[x][0])
        add[ch[x][0]] = (add[ch[x][0]] + add[x]) % mod,
        val[ch[x][0]] = (val[ch[x][0]] + add[x]) % mod,
        sum[ch[x][0]] = (sum[ch[x][0]] + add[x] * siz[ch[x][0]] % mod) % mod;
      if (ch[x][1])
        add[ch[x][1]] = (add[ch[x][1]] + add[x]) % mod,
        val[ch[x][1]] = (val[ch[x][1]] + add[x]) % mod,
        sum[ch[x][1]] = (sum[ch[x][1]] + add[x] * siz[ch[x][1]] % mod) % mod;
      add[x] = 0;
    }
    if (rev[x]) {
      if (ch[x][0]) rev[ch[x][0]] ^= 1, swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
      if (ch[x][1]) rev[ch[x][1]] ^= 1, swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
      rev[x] = 0;
    }
  }

  void update(long long x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void print(long long x) {
    if (!x) return;
    pushdown(x);
    print(ch[x][0]);
    printf("%lld ", x);
    print(ch[x][1]);
  }

  void rotate(long long x) {
    long long y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    maintain(z);
  }

  void splay(long long x) {
    update(x);
    for (long long f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(long long x) {
    for (long long f = 0; x; f = x, x = fa[x])
      splay(x), ch[x][1] = f, maintain(x);
  }

  void makeroot(long long x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    rev[x] ^= 1;
  }

  long long find(long long x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
} st;

main() {
  scanf("%lld%lld", &n, &q);
  for (long long i = 1; i <= n; i++) st.val[i] = 1, st.maintain(i);
  for (long long i = 1; i < n; i++) {
    scanf("%lld%lld", &u, &v);
    if (st.find(u) != st.find(v)) st.makeroot(u), st.fa[u] = v;
  }
  while (q--) {
    scanf(" %c%lld%lld", &op, &u, &v);
    if (op == '+') {
      scanf("%lld", &c);
      st.makeroot(u), st.access(v), st.splay(v);
      st.val[v] = (st.val[v] + c) % mod;
      st.sum[v] = (st.sum[v] + st.siz[v] * c % mod) % mod;
      st.add[v] = (st.add[v] + c) % mod;
    }
    if (op == '-') {
      st.makeroot(u);
      st.access(v);
      st.splay(v);
      if (st.ch[v][0] == u && !st.ch[u][1]) st.ch[v][0] = st.fa[u] = 0;
      scanf("%lld%lld", &u, &v);
      if (st.find(u) != st.find(v)) st.makeroot(u), st.fa[u] = v;
    }
    if (op == '*') {
      scanf("%lld", &c);
      st.makeroot(u), st.access(v), st.splay(v);
      st.val[v] = st.val[v] * c % mod;
      st.sum[v] = st.sum[v] * c % mod;
      st.mul[v] = st.mul[v] * c % mod;
    }
    if (op == '/')
      st.makeroot(u), st.access(v), st.splay(v), printf("%lld\n", st.sum[v]);
  }
  return 0;
}

Practice problems

Maintaining connectivity

Testing connectivity

The LCT's Find() function tells whether two nodes of a dynamic forest are connected: if Find(x)==Find(y), then \(x\) and \(y\) are in the same tree and hence connected.

Example: [SDOI2008] Cave Survey

Initially there are \(n\) isolated nodes. Then come \(m\) operations, each of one of the following kinds:

  1. Connect u v: add an edge between \(u\) and \(v\).
  2. Destroy u v: delete the edge between \(u\) and \(v\); such an edge is guaranteed to exist.
  3. Query u v: ask whether \(u\) and \(v\) are connected.

The graph is guaranteed to be a forest at all times.

\(n\le 10^4, m\le 2\times 10^5\)

Reference code
 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
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
constexpr int MAXN = 10010;

struct Splay {
  int ch[MAXN][2], fa[MAXN], tag[MAXN];

  void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = tag[x] = 0; }

  int getch(int x) { return ch[fa[x]][1] == x; }

  int isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) swap(ch[ch[x][0]][0], ch[ch[x][0]][1]), tag[ch[x][0]] ^= 1;
      if (ch[x][1]) swap(ch[ch[x][1]][0], ch[ch[x][1]][1]), tag[ch[x][1]] ^= 1;
      tag[x] = 0;
    }
  }

  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
  }

  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(int x) {
    for (int f = 0; x; f = x, x = fa[x]) splay(x), ch[x][1] = f;
  }

  void makeroot(int x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    tag[x] ^= 1;
  }

  int find(int x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
} st;

int n, q, x, y;
char op[MAXN];

int main() {
  scanf("%d%d", &n, &q);
  while (q--) {
    scanf("%s%d%d", op, &x, &y);
    if (op[0] == 'Q') {
      if (st.find(x) == st.find(y))
        printf("Yes\n");
      else
        printf("No\n");
    }
    if (op[0] == 'C')
      if (st.find(x) != st.find(y)) st.makeroot(x), st.fa[x] = y;
    if (op[0] == 'D') {
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      if (st.ch[y][0] == x && !st.ch[x][1]) st.ch[y][0] = st.fa[x] = 0;
    }
  }
  return 0;
}

Maintaining 2-edge-connected components

Suppose every 2-edge-connected component has to be contracted into a single node. Whenever an edge is added between two nodes of the tree that are already connected, all nodes on the path between them are contracted into one.

Example: [AHOI2005] Route Planning

You are given \(n\) nodes and, initially, \(m\) undirected edges. Then come \(q\) operations, each of one of the following kinds:

  1. 0 u v: delete the edge between \(u\) and \(v\); such an edge is guaranteed to exist at that moment.
  2. 1 u v: report the number of edges that every possible path between \(u\) and \(v\) must pass through at that moment.

The graph is guaranteed to be connected at all times.

\(1<n<3\times 10^4,1<m<10^5,0\le q\le 4\times 10^4\)

Contract every 2-edge-connected component into a single node. The number of edges that every possible path between \(u\) and \(v\) must pass through is then (the number of nodes on the path between the node containing \(u\) and the node containing \(v\)) \(-1\).

Deleting edges is hard to handle here, so we go offline and process the operations in reverse, turning deletions into insertions.

When an edge is added, if its endpoints were not connected, link them in the LCT. Otherwise, extract the path between them as it was in the LCT before this edge, and traverse the corresponding subtree of the auxiliary tree, which amounts to traversing the path. Merge all these nodes, and keep track of the merges with a disjoint set union.

The representative of the merged set in the disjoint set union then stands for the whole path of the tree. From here on, every operation must first find the representatives of its nodes in the disjoint set union and operate on those.

Reference code
  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
163
164
165
166
167
168
169
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
constexpr int MAXN = 200010;
int f[MAXN];

int findp(int x) { return f[x] ? f[x] = findp(f[x]) : x; }

void merge(int x, int y) {
  x = findp(x);
  y = findp(y);
  if (x != y) f[x] = y;
}

struct Splay {
  int ch[MAXN][2], fa[MAXN], tag[MAXN], siz[MAXN];

  void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = tag[x] = siz[x] = 0; }

  int getch(int x) { return ch[findp(fa[x])][1] == x; }

  int isroot(int x) {
    return ch[findp(fa[x])][0] != x && ch[findp(fa[x])][1] != x;
  }

  void maintain(int x) {
    clear(0);
    if (x) siz[x] = siz[ch[x][0]] + 1 + siz[ch[x][1]];
  }

  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) tag[ch[x][0]] ^= 1, swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
      if (ch[x][1]) tag[ch[x][1]] ^= 1, swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
      tag[x] = 0;
    }
  }

  void print(int x) {
    if (!x) return;
    pushdown(x);
    print(ch[x][0]);
    printf("%d ", x);
    print(ch[x][1]);
  }

  void update(int x) {
    if (!isroot(x)) update(findp(fa[x]));
    pushdown(x);
  }

  void rotate(int x) {
    x = findp(x);
    int y = findp(fa[x]), z = findp(fa[y]), chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    if (z) maintain(z);
  }

  void splay(int x) {
    x = findp(x);
    update(x);
    for (int f = findp(fa[x]); f = findp(fa[x]), !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(int x) {
    for (int f = 0; x; f = x, x = findp(fa[x]))
      splay(x), ch[x][1] = f, maintain(x);
  }

  void makeroot(int x) {
    x = findp(x);
    access(x);
    splay(x);
    tag[x] ^= 1;
    swap(ch[x][0], ch[x][1]);
  }

  int find(int x) {
    x = findp(x);
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }

  void dfs(int x) {
    pushdown(x);
    if (ch[x][0]) dfs(ch[x][0]), merge(ch[x][0], x);
    if (ch[x][1]) dfs(ch[x][1]), merge(ch[x][1], x);
  }
} st;

int n, m, q, x, y, cur, ans[MAXN];

struct oper {
  int op, a, b;
} s[MAXN];

map<pair<int, int>, int> mp;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) st.maintain(i);
  for (int i = 1; i <= m; i++)
    scanf("%d%d", &x, &y), mp[{x, y}] = mp[{y, x}] = 1;
  while (scanf("%d", &s[++q].op)) {
    if (s[q].op == -1) {
      q--;
      break;
    }
    scanf("%d%d", &s[q].a, &s[q].b);
    if (!s[q].op) mp[{s[q].a, s[q].b}] = mp[{s[q].b, s[q].a}] = 0;
  }
  reverse(s + 1, s + q + 1);
  for (map<pair<int, int>, int>::iterator it = mp.begin(); it != mp.end(); it++)
    if (it->second) {
      mp[{it->first.second, it->first.first}] = 0;
      x = findp(it->first.first);
      y = findp(it->first.second);
      if (st.find(x) != st.find(y))
        st.makeroot(x), st.fa[x] = y;
      else {
        if (x == y) continue;
        st.makeroot(x);
        st.access(y);
        st.splay(y);
        st.dfs(y);
        int t = findp(y);
        st.fa[t] = findp(st.fa[y]);
        st.ch[t][0] = st.ch[t][1] = 0;
        st.maintain(t);
      }
    }
  for (int i = 1; i <= q; i++) {
    if (s[i].op == 0) {
      x = findp(s[i].a);
      y = findp(s[i].b);
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      st.dfs(y);
      int t = findp(y);
      st.fa[t] = st.fa[y];
      st.ch[t][0] = st.ch[t][1] = 0;
      st.maintain(t);
    }
    if (s[i].op == 1) {
      x = findp(s[i].a);
      y = findp(s[i].b);
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      ans[++cur] = st.siz[y] - 1;
    }
  }
  for (int i = cur; i >= 1; i--) printf("%d\n", ans[i]);
  return 0;
}

Practice problems

Maintaining edge weights

An LCT cannot handle edge weights directly. Instead, create a node for each edge, which makes the edges on a path easy to query. With this trick, a spanning tree can be maintained dynamically.

Example: Luogu P4234 Minimum Difference Spanning Tree

Given a weighted undirected graph with \(n\) vertices and \(m\) edges, find a spanning tree that minimizes the difference between its largest and smallest edge weights, and print that difference.

The input guarantees that at least one spanning tree exists.

\(1\le n\le 5\times 10^4,1\le m\le 2\times 10^5,1\le w_i\le 10^4\)

Sort the edges by weight in increasing order and enumerate the rightmost edge chosen. For the best answer, the smallest edge weight in the tree must be as large as possible.

Add the edges in this order. If the two endpoints of the new edge are already connected, delete the edge of smallest weight on the path between them. Once the whole graph is connected into a tree, update the answer with the current edge weight minus the smallest edge weight. The smallest edge weight can be maintained with two pointers.

An LCT has no fixed parent-child relation, so an edge weight cannot be stored as a vertex weight.

To record information about the edges on a tree path, use edge splitting: create a node for each edge and connect it to both endpoints of the edge. Every link and every cut then becomes two operations.

Reference code
  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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
constexpr int MAXN = 5000010;

struct Splay {
  int ch[MAXN][2], fa[MAXN], tag[MAXN], val[MAXN], minn[MAXN];

  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = tag[x] = val[x] = minn[x] = 0;
  }

  int getch(int x) { return ch[fa[x]][1] == x; }

  int isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

  void maintain(int x) {
    if (!x) return;
    minn[x] = x;
    if (ch[x][0]) {
      if (val[minn[ch[x][0]]] < val[minn[x]]) minn[x] = minn[ch[x][0]];
    }
    if (ch[x][1]) {
      if (val[minn[ch[x][1]]] < val[minn[x]]) minn[x] = minn[ch[x][1]];
    }
  }

  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) tag[ch[x][0]] ^= 1, swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
      if (ch[x][1]) tag[ch[x][1]] ^= 1, swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
      tag[x] = 0;
    }
  }

  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void print(int x) {
    if (!x) return;
    pushdown(x);
    print(ch[x][0]);
    printf("%d ", x);
    print(ch[x][1]);
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    if (z) maintain(z);
  }

  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(int x) {
    for (int f = 0; x; f = x, x = fa[x]) splay(x), ch[x][1] = f, maintain(x);
  }

  void makeroot(int x) {
    access(x);
    splay(x);
    tag[x] ^= 1;
    swap(ch[x][0], ch[x][1]);
  }

  int find(int x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }

  void link(int x, int y) {
    makeroot(x);
    fa[x] = y;
  }

  void cut(int x, int y) {
    makeroot(x);
    access(y);
    splay(y);
    ch[y][0] = fa[x] = 0;
    maintain(y);
  }
} st;

constexpr int inf = 2e9 + 1;
int n, m, ans, nww, x, y;

struct Edge {
  int u, v, w;

  bool operator<(Edge x) const { return w < x.w; };
} s[MAXN];

multiset<int> mp;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) st.val[i] = inf, st.maintain(i);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &s[i].u, &s[i].v, &s[i].w);
  sort(s + 1, s + m + 1);
  for (int i = 1; i <= m; i++) st.val[n + i] = s[i].w, st.maintain(n + i);
  for (int i = 1; i <= m; i++) {
    x = s[i].u;
    y = s[i].v;
    if (x == y) continue;
    if (st.find(x) != st.find(y)) {
      nww++;
      st.link(x, n + i);
      st.link(n + i, y);
      mp.insert(s[i].w);
      if (nww == n - 1) ans = s[i].w - (*(mp.begin()++));
    } else {
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      int t = st.minn[y] - n;
      st.cut(s[t].u, t + n);
      st.cut(t + n, s[t].v);
      mp.erase(mp.find(s[t].w));
      st.link(x, n + i);
      st.link(n + i, y);
      mp.insert(s[i].w);
      if (nww == n - 1) ans = min(ans, s[i].w - (*(mp.begin()++)));
    }
  }
  printf("%d\n", ans);
  return 0;
}

Practice problems

Maintaining subtree information

Subtree information is not the LCT's strength. But by aggregating, at each node, the information of all its virtual subtrees, we can obtain the information of the whole tree.

Example: [BJOI2014] Great Merge

You are given \(n\) nodes and \(q\) operations, each of one of the following forms:

  1. A x y: add an edge between nodes \(x\) and \(y\).
  2. Q x y: given an existing edge \((x,y)\), count the simple paths that contain the edge \((x,y)\).

The graph is guaranteed to be a forest at all times.

\(1\le n,q,x,y\le 10^5\)

Restate the query Q: the answer is the number of nodes on the \(x\) side of the edge \((x,y)\) times the number of nodes on the \(y\) side, that is, the sizes of the trees containing \(x\) and \(y\) once the edge \((x,y)\) is cut. To undo the effect of the cut, we link \((x,y)\) again after the query.

The operations add edges and delete edges, and the graph is guaranteed to be a forest at all times, so an LCT comes to mind at once. But here the LCT has to maintain subtree sizes, not the information along a path that we are used to, and in the construction of an LCT the child knows its parent but the parent does not know the child, which makes it awkward to aggregate over subtrees directly. What can we do?

The answer is to keep, for each node \(x\), the contribution of the subtrees represented by all its virtual children (nodes whose parent is \(x\) but which are neither the left nor the right child of \(x\) in its splay tree).

Let \(siz2[x]\) be the number of nodes in the subtrees represented by all virtual children of node \(x\), and let \(siz[x]\) be the number of nodes in the subtree of \(x\).

Unlike the usual way of maintaining subtree sizes in a splay tree, the number of nodes in the subtree of \(x\) now also includes \(siz2[x]\):

1
2
3
4
void maintain(int x) {
  clear(0);
  if (x) siz[x] = siz[ch[x][0]] + 1 + siz[ch[x][1]] + siz2[x];
}

Moreover, whenever we change the shape of a splay tree (that is, change the left or right child pointer of a node in it), \(siz2[x]\) must be updated right away.

In Rotate() and Splay() we only change the relative positions of nodes inside a splay tree. No edge switches between virtual and preferred, so \(siz2[x]\) is left alone.

In access, every splay is followed by a change of the right child of the node just splayed. The edge to its old right child and the edge to its new right child both switch between virtual and preferred, so we add the contribution of the subtree whose edge has just become virtual and subtract that of the subtree whose edge has just become preferred. The code:

1
2
3
4
void access(int x) {
  for (int f = 0; x; f = x, x = fa[x])
    splay(x), siz2[x] += siz[ch[x][1]] - siz[f], ch[x][1] = f, maintain(x);
}

In MakeRoot() and Find() we only call the earlier functions or walk along edges of a splay tree, so nothing needs to change.

When two nodes are linked, one node gets a new parent, and the size of the new child's subtree must be added to the \(siz2\) value of that parent.

1
2
3
4
st.makeroot(x);
st.makeroot(y);
st.fa[x] = y;
st.siz2[y] += st.siz[x];

When an edge is cut, we only remove a preferred edge inside a splay tree. Maintain takes care of the information, and nothing else needs to change.

Those are the changes to the code. To finish, here is a summary of what an LCT needs in order to maintain subtree information, and how it is done:

  1. The information must be subtractable, like the number of nodes or the sum of weights in a subtree. A subtree maximum or minimum cannot be maintained directly, because when a virtual edge becomes preferred, its former contribution has to be removed.
  2. Keep an extra value that stores the contribution of the virtual subtrees. Add it to the node's own answer when aggregating, and update it whenever an edge switches between virtual and preferred.
  3. Everything else is as in an ordinary LCT. To read off the information of a subtree, always make its node the root first.
  4. If the information is not subtractable, such as a range minimum/maximum, give each node a balanced tree that maintains the minimum or maximum over its virtual subtrees.
Reference code
  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
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
constexpr int MAXN = 100010;
using ll = long long;

struct Splay {
  int ch[MAXN][2], fa[MAXN], siz[MAXN], siz2[MAXN], tag[MAXN];

  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = siz[x] = siz2[x] = tag[x] = 0;
  }

  int getch(int x) { return ch[fa[x]][1] == x; }

  int isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }

  void maintain(int x) {
    clear(0);
    if (x) siz[x] = siz[ch[x][0]] + 1 + siz[ch[x][1]] + siz2[x];
  }

  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) swap(ch[ch[x][0]][0], ch[ch[x][0]][1]), tag[ch[x][0]] ^= 1;
      if (ch[x][1]) swap(ch[ch[x][1]][0], ch[ch[x][1]][1]), tag[ch[x][1]] ^= 1;
      tag[x] = 0;
    }
  }

  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    maintain(z);
  }

  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(int x) {
    for (int f = 0; x; f = x, x = fa[x])
      splay(x), siz2[x] += siz[ch[x][1]] - siz[f], ch[x][1] = f, maintain(x);
  }

  void makeroot(int x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    tag[x] ^= 1;
  }

  int find(int x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
} st;

int n, q, x, y;
char op;

int main() {
  scanf("%d%d", &n, &q);
  while (q--) {
    scanf(" %c%d%d", &op, &x, &y);
    if (op == 'A') {
      st.makeroot(x);
      st.makeroot(y);
      st.fa[x] = y;
      st.siz2[y] += st.siz[x];
    }
    if (op == 'Q') {
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      st.ch[y][0] = st.fa[x] = 0;
      st.maintain(x);
      st.makeroot(x);
      st.makeroot(y);
      printf("%lld\n", (ll)(st.siz[x] * st.siz[y]));
      st.makeroot(x);
      st.makeroot(y);
      st.fa[x] = y;
      st.siz2[y] += st.siz[x];
    }
  }
  return 0;
}

Practice problems