31.05Intermediate / Advanced5 topics17 min4 interactive animations

Advanced DSU variants

Variants of union-find that undo unions, track parity or numeric differences, carry extra data per set, and a note on what 'DSU on tree' really means.

Learning goals

Undo unions with a rollback DSU and know why compression is not allowed
Detect odd cycles with a parity DSU
Keep value differences with a weighted (potential) DSU
Maintain per-set metadata and tell DSU on tree from union-find

Prerequisites

OptimizationsBipartite graphsStack

The plain structure answers one question: same set or not. Attach a little more information to each parent link, and the same tree can also say 'different colour', 'five more than' or 'undo that last merge'.

31.05.1

Rollback DSU

A **rollback DSU** can undo the most recent union. Union by size changes exactly one parent entry and one size entry, so push those two facts on a stack and, to undo, pop them and restore the values. Path compression changes many entries at once and cannot be undone cheaply, so a rollback DSU uses union by size alone; find then costs O(log n).

It is the tool for offline divide-and-conquer over time: add edges while descending a segment tree over time, answer at the leaves, undo while coming back up. In the animation's "Rollback: unite, then undo" preset, three unions 0-1 2-3 1-2 give one big set, the undo pops the last merge and splits it back, and the final 0?3 query shows 0 and 3 not connected.

Java

1class RollbackDsu {
2    final int[] parent, size;
3    private final Deque<int[]> history = new ArrayDeque<>();      // each entry {child root, parent root}
4    int components;
5    RollbackDsu(int n) {
6        parent = new int[n]; size = new int[n]; components = n;
7        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
8    }
9    int find(int x) { while (parent[x] != x) x = parent[x]; return x; }   // no path compression: it could not be undone
10    boolean union(int a, int b) {
11        int ra = find(a), rb = find(b);
12        if (ra == rb) return false;
13        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
14        parent[rb] = ra; size[ra] += size[rb];
15        history.push(new int[]{rb, ra});         // remember exactly what changed
16        components--;
17        return true;
18    }
19    void undo() {                                // reverts the most recent successful union
20        int[] h = history.pop();
21        size[h[1]] -= size[h[0]];
22        parent[h[0]] = h[0];
23        components++;
24    }
25}

Union-find variants: rollback, parity and weighted (potential) DSU

Interactive · edit the input

forest (no compression, so every union can be undone) · 6 nodes

size 1

Consistent / connectedJust changedConflict or undoneBeing followedA root

parent[x]

history stack (child root → parent root), top last

empty

Setup

A rollback DSU unites by size and never compresses paths, so each union changes exactly one parent and one size. A stack of those changes lets undo() restore the previous state exactly, which is the basis of offline divide-and-conquer on time.

Step 1 / 8

Java

1int[] parent, size; Deque<int[]> history = new ArrayDeque<>();      // each entry {child root, parent root}
2int find(int x) { while (parent[x] != x) x = parent[x]; return x; }     // no path compression: it could not be undone
3boolean union(int a, int b) {
4    int ra = find(a), rb = find(b);
5    if (ra == rb) return false;
6    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
7    parent[rb] = ra; size[ra] += size[rb];
8    history.push(new int[]{rb, ra});             // remember exactly what changed
9    return true;
10}
11void undo() {
12    int[] h = history.pop();
13    size[h[1]] -= size[h[0]]; parent[h[0]] = h[0];
14}
15int[] parent, parity;                            // parity[x]: 0 if x has the same colour as parent[x], 1 if different
16int find(int x) {                                // returns the root; afterwards parity[x] is relative to it
17    if (parent[x] == x) return x;
18    int p = parent[x], root = find(p);
19    parity[x] ^= parity[p]; parent[x] = root;
20    return root;
21}
22boolean addDifferent(int a, int b) {             // a and b must get different colours; false on conflict
23    int ra = find(a), rb = find(b);
24    if (ra == rb) return parity[a] != parity[b];      // same set: they must already differ
25    parent[ra] = rb; parity[ra] = parity[a] ^ parity[b] ^ 1;
26    return true;
27}
28int[] parent; long[] diff;                       // diff[x] = value[x] - value[parent[x]]
29int find(int x) {
30    if (parent[x] == x) return x;
31    int p = parent[x], root = find(p);
32    diff[x] += diff[p]; parent[x] = root;        // now relative to the root
33    return root;
34}
35boolean addConstraint(int a, int b, long d) {    // value[b] - value[a] == d
36    int ra = find(a), rb = find(b);
37    if (ra == rb) return diff[b] - diff[a] == d;
38    parent[rb] = ra; diff[rb] = diff[a] + d - diff[b];      // value[rb] - value[ra]
39    return true;
40}
41Long query(int a, int b) { return find(a) == find(b) ? diff[b] - diff[a] : null; }

Live state

0 unions0 undos6 components

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L1	n=6	A rollback DSU unites by size and never compresses paths, so each union changes exactly one parent and one size. A stack of those changes lets undo() restore the previous state exactly, which is the basis of offline divide-and-conquer on time.
2	L8	op=0-1 pushed=1→0 components=5	0-1: unite by size: parent[1] = 0, size[0] = 2. Push {1 → 0} on the history.
3	L8	op=2-3 pushed=3→2 components=4	2-3: unite by size: parent[3] = 2, size[2] = 2. Push {3 → 2} on the history.
4	L8	op=1-2 pushed=2→0 components=3	1-2: unite by size: parent[2] = 0, size[0] = 4. Push {2 → 0} on the history.
5	L13	op=undo restored=2 components=4	undo: pop {2 → 0}: 2 becomes a root again and 0 loses its size. The state is exactly as before that union.
6	L8	op=4-5 pushed=5→4 components=3	4-5: unite by size: parent[5] = 4, size[4] = 2. Push {5 → 4} on the history.
7	L2	op=0?3 connected=false	0?3: roots 0 and 2: not connected.
8	L14	return=3 unions=4 undos=1	3 sets remain after 4 unions and 1 undo. Find costs O(log n) without compression, but every change can be reverted.

31.05.2

Parity DSU

A **parity DSU** stores, for each element, whether its colour differs from its parent's. The parity of an element relative to its root is the XOR of the parities on the path, and path compression keeps it correct by XOR-ing as it re-points. An edge a-b that must join two different colours is consistent if the sets differ (link them with the right parity) or, when both are in one set, if their parities relative to the root differ. Otherwise there is an odd cycle: the graph is not bipartite.

The animation's "Parity: an even cycle is bipartite" preset (0-1 1-2 2-3 3-0) is accepted, while "Parity: an odd cycle conflicts" (0-1 1-2 2-0 2-3) stops at 2-0, which closes a triangle. Parity DSU also answers online 'is the graph still bipartite after adding this edge?' in near-constant time per edge.

Java

1class ParityDsu {
2    final int[] parent, parity;                  // parity[x]: 0 if x has the same colour as parent[x], 1 if different
3    ParityDsu(int n) {
4        parent = new int[n]; parity = new int[n];
5        for (int i = 0; i < n; i++) parent[i] = i;
6    }
7    int find(int x) {                            // returns the root; afterwards parity[x] is relative to it
8        if (parent[x] == x) return x;
9        int p = parent[x], root = find(p);
10        parity[x] ^= parity[p];
11        parent[x] = root;
12        return root;
13    }
14    boolean addDifferent(int a, int b) {         // a and b must get different colours; false on conflict
15        int ra = find(a), rb = find(b);
16        if (ra == rb) return parity[a] != parity[b];
17        parent[ra] = rb;
18        parity[ra] = parity[a] ^ parity[b] ^ 1;
19        return true;
20    }
21}

Union-find variants: rollback, parity and weighted (potential) DSU

Interactive · edit the input

forest (no compression, so every union can be undone) · 6 nodes

size 1

Consistent / connectedJust changedConflict or undoneBeing followedA root

parent[x]

history stack (child root → parent root), top last

empty

Setup

Step 1 / 8

Java

1int[] parent, size; Deque<int[]> history = new ArrayDeque<>();      // each entry {child root, parent root}
2int find(int x) { while (parent[x] != x) x = parent[x]; return x; }     // no path compression: it could not be undone
3boolean union(int a, int b) {
4    int ra = find(a), rb = find(b);
5    if (ra == rb) return false;
6    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
7    parent[rb] = ra; size[ra] += size[rb];
8    history.push(new int[]{rb, ra});             // remember exactly what changed
9    return true;
10}
11void undo() {
12    int[] h = history.pop();
13    size[h[1]] -= size[h[0]]; parent[h[0]] = h[0];
14}
15int[] parent, parity;                            // parity[x]: 0 if x has the same colour as parent[x], 1 if different
16int find(int x) {                                // returns the root; afterwards parity[x] is relative to it
17    if (parent[x] == x) return x;
18    int p = parent[x], root = find(p);
19    parity[x] ^= parity[p]; parent[x] = root;
20    return root;
21}
22boolean addDifferent(int a, int b) {             // a and b must get different colours; false on conflict
23    int ra = find(a), rb = find(b);
24    if (ra == rb) return parity[a] != parity[b];      // same set: they must already differ
25    parent[ra] = rb; parity[ra] = parity[a] ^ parity[b] ^ 1;
26    return true;
27}
28int[] parent; long[] diff;                       // diff[x] = value[x] - value[parent[x]]
29int find(int x) {
30    if (parent[x] == x) return x;
31    int p = parent[x], root = find(p);
32    diff[x] += diff[p]; parent[x] = root;        // now relative to the root
33    return root;
34}
35boolean addConstraint(int a, int b, long d) {    // value[b] - value[a] == d
36    int ra = find(a), rb = find(b);
37    if (ra == rb) return diff[b] - diff[a] == d;
38    parent[rb] = ra; diff[rb] = diff[a] + d - diff[b];      // value[rb] - value[ra]
39    return true;
40}
41Long query(int a, int b) { return find(a) == find(b) ? diff[b] - diff[a] : null; }

Live state

0 unions0 undos6 components

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L1	n=6	A rollback DSU unites by size and never compresses paths, so each union changes exactly one parent and one size. A stack of those changes lets undo() restore the previous state exactly, which is the basis of offline divide-and-conquer on time.
2	L8	op=0-1 pushed=1→0 components=5	0-1: unite by size: parent[1] = 0, size[0] = 2. Push {1 → 0} on the history.
3	L8	op=2-3 pushed=3→2 components=4	2-3: unite by size: parent[3] = 2, size[2] = 2. Push {3 → 2} on the history.
4	L8	op=1-2 pushed=2→0 components=3	1-2: unite by size: parent[2] = 0, size[0] = 4. Push {2 → 0} on the history.
5	L13	op=undo restored=2 components=4	undo: pop {2 → 0}: 2 becomes a root again and 0 loses its size. The state is exactly as before that union.
6	L8	op=4-5 pushed=5→4 components=3	4-5: unite by size: parent[5] = 4, size[4] = 2. Push {5 → 4} on the history.
7	L2	op=0?3 connected=false	0?3: roots 0 and 2: not connected.
8	L14	return=3 unions=4 undos=1	3 sets remain after 4 unions and 1 undo. Find costs O(log n) without compression, but every change can be reverted.

31.05.3

Weighted/potential DSU

A **weighted** (potential) DSU stores for each element the difference diff[x] = value[x] - value[parent[x]]. Constraints of the form value[b] - value[a] = d then join sets and fix the offset between their roots, and any later query value[b] - value[a] inside one set is diff[b] - diff[a] after the finds. A constraint inside a set is consistent only if it matches the stored difference: otherwise the system is contradictory.

Typical uses: ratios between variables (take logarithms or work with fractions), distances along a line, 'A is heavier than B by 3'. In the preset "Weighted: consistent differences" (0-1:3 1-2:2) the query 0?2 returns 5, 2?0 returns -5, and 0?4 is unknown because 4 is in no set with 0. "Weighted: a contradiction" shows 0-2:4 rejected after 5 was already implied.

Java

1class WeightedDsu {
2    final int[] parent;
3    final long[] diff;                           // diff[x] = value[x] - value[parent[x]]
4    WeightedDsu(int n) {
5        parent = new int[n]; diff = new long[n];
6        for (int i = 0; i < n; i++) parent[i] = i;
7    }
8    int find(int x) {
9        if (parent[x] == x) return x;
10        int p = parent[x], root = find(p);
11        diff[x] += diff[p];                      // now relative to the root
12        parent[x] = root;
13        return root;
14    }
15    boolean addConstraint(int a, int b, long d) {          // value[b] - value[a] == d; false on a contradiction
16        int ra = find(a), rb = find(b);
17        if (ra == rb) return diff[b] - diff[a] == d;
18        parent[rb] = ra;
19        diff[rb] = diff[a] + d - diff[b];        // value[rb] - value[ra]
20        return true;
21    }
22    Long query(int a, int b) { return find(a) == find(b) ? diff[b] - diff[a] : null; }   // null: not related
23}

Union-find variants: rollback, parity and weighted (potential) DSU

Interactive · edit the input

forest (no compression, so every union can be undone) · 6 nodes

size 1

Consistent / connectedJust changedConflict or undoneBeing followedA root

parent[x]

history stack (child root → parent root), top last

empty

Setup

Step 1 / 8

Java

1int[] parent, size; Deque<int[]> history = new ArrayDeque<>();      // each entry {child root, parent root}
2int find(int x) { while (parent[x] != x) x = parent[x]; return x; }     // no path compression: it could not be undone
3boolean union(int a, int b) {
4    int ra = find(a), rb = find(b);
5    if (ra == rb) return false;
6    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
7    parent[rb] = ra; size[ra] += size[rb];
8    history.push(new int[]{rb, ra});             // remember exactly what changed
9    return true;
10}
11void undo() {
12    int[] h = history.pop();
13    size[h[1]] -= size[h[0]]; parent[h[0]] = h[0];
14}
15int[] parent, parity;                            // parity[x]: 0 if x has the same colour as parent[x], 1 if different
16int find(int x) {                                // returns the root; afterwards parity[x] is relative to it
17    if (parent[x] == x) return x;
18    int p = parent[x], root = find(p);
19    parity[x] ^= parity[p]; parent[x] = root;
20    return root;
21}
22boolean addDifferent(int a, int b) {             // a and b must get different colours; false on conflict
23    int ra = find(a), rb = find(b);
24    if (ra == rb) return parity[a] != parity[b];      // same set: they must already differ
25    parent[ra] = rb; parity[ra] = parity[a] ^ parity[b] ^ 1;
26    return true;
27}
28int[] parent; long[] diff;                       // diff[x] = value[x] - value[parent[x]]
29int find(int x) {
30    if (parent[x] == x) return x;
31    int p = parent[x], root = find(p);
32    diff[x] += diff[p]; parent[x] = root;        // now relative to the root
33    return root;
34}
35boolean addConstraint(int a, int b, long d) {    // value[b] - value[a] == d
36    int ra = find(a), rb = find(b);
37    if (ra == rb) return diff[b] - diff[a] == d;
38    parent[rb] = ra; diff[rb] = diff[a] + d - diff[b];      // value[rb] - value[ra]
39    return true;
40}
41Long query(int a, int b) { return find(a) == find(b) ? diff[b] - diff[a] : null; }

Live state

0 unions0 undos6 components

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L1	n=6	A rollback DSU unites by size and never compresses paths, so each union changes exactly one parent and one size. A stack of those changes lets undo() restore the previous state exactly, which is the basis of offline divide-and-conquer on time.
2	L8	op=0-1 pushed=1→0 components=5	0-1: unite by size: parent[1] = 0, size[0] = 2. Push {1 → 0} on the history.
3	L8	op=2-3 pushed=3→2 components=4	2-3: unite by size: parent[3] = 2, size[2] = 2. Push {3 → 2} on the history.
4	L8	op=1-2 pushed=2→0 components=3	1-2: unite by size: parent[2] = 0, size[0] = 4. Push {2 → 0} on the history.
5	L13	op=undo restored=2 components=4	undo: pop {2 → 0}: 2 becomes a root again and 0 loses its size. The state is exactly as before that union.
6	L8	op=4-5 pushed=5→4 components=3	4-5: unite by size: parent[5] = 4, size[4] = 2. Push {5 → 4} on the history.
7	L2	op=0?3 connected=false	0?3: roots 0 and 2: not connected.
8	L14	return=3 unions=4 undos=1	3 sets remain after 4 unions and 1 undo. Find costs O(log n) without compression, but every change can be reverted.

31.05.4

DSU with metadata

Any summary that can be merged can be stored at the root of each set: the size, the smallest or largest member, the sum of the members, the number of edges, a bitmask. When two sets are united, combine the metadata of the two roots into the new root. Queries read the root's data after a find. The cost stays near-constant per operation if the merge is O(1).

The code keeps the size, the minimum element and the sum for every set. Remember to update only the surviving root and to read from the root, never from other members; their copies may be stale.

Java

1class MetaDsu {
2    final int[] parent, size, min;
3    final long[] sum;
4    MetaDsu(int n) {
5        parent = new int[n]; size = new int[n]; min = new int[n]; sum = new long[n];
6        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; min[i] = i; sum[i] = i; }
7    }
8    int find(int x) {
9        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
10        return x;
11    }
12    boolean union(int a, int b) {
13        int ra = find(a), rb = find(b);
14        if (ra == rb) return false;
15        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
16        parent[rb] = ra;
17        size[ra] += size[rb];
18        min[ra] = Math.min(min[ra], min[rb]);    // combine the metadata of the two roots
19        sum[ra] += sum[rb];
20        return true;
21    }
22    int sizeOf(int x) { return size[find(x)]; }
23    int minOf(int x) { return min[find(x)]; }
24    long sumOf(int x) { return sum[find(x)]; }
25}

Union-find: find, union, path compression, union by size and rank

Interactive · edit the input

disjoint-set forest (arrow = parent, roots on top) · 6 nodes

Being followedParent just changedRoot foundAlready connectedA root (set representative)

parent[x]

Setup

6 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.

Step 1 / 25

Java

1int[] parent, size, rank;                        // parent[x] == x for a root
2int findPlain(int x) { while (parent[x] != x) x = parent[x]; return x; }          // follow parents to the root
3int findCompress(int x) {                        // path compression: point everyone on the path at the root
4    if (parent[x] != x) parent[x] = findCompress(parent[x]);
5    return parent[x];
6}
7int findHalving(int x) {                         // path halving: skip one level as you climb
8    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
9    return x;
10}
11boolean unionNaive(int a, int b) {               // link the first root under the second
12    int ra = find(a), rb = find(b);
13    if (ra == rb) return false;
14    parent[ra] = rb;
15    return true;
16}
17boolean unionBySize(int a, int b) {              // the smaller tree goes under the larger
18    int ra = find(a), rb = find(b);
19    if (ra == rb) return false;
20    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
21    parent[rb] = ra; size[ra] += size[rb];
22    return true;
23}
24boolean unionByRank(int a, int b) {              // the lower-rank root goes under the higher one
25    int ra = find(a), rb = find(b);
26    if (ra == rb) return false;
27    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
28    parent[rb] = ra;
29    if (rank[ra] == rank[rb]) rank[ra]++;
30    return true;
31}

Live state

0 find hops0 parent changes6 components

components

No condition evaluated on this step

Execution trace (dry run table)Show 25 steps

Step	Line	State	What happens
1	L1	n=6 components=6	6 elements, each in its own set: parent[x] = x makes every element a root (the set's representative). Union links one root under the other with no balancing.
2	L2	who=find(0) root=0	find(0): 0 is its own parent: it is the root.
3	L2	who=find(1) root=1	find(1): 1 is its own parent: it is the root.
4	L14	op=0-1 child=0 top=1 components=5	0-1: parent[0] = 1: the root of the first element goes under the root of the second. 5 sets left.
5	L2	who=find(1) root=1	find(1): 1 is its own parent: it is the root.
6	L2	who=find(2) root=2	find(2): 2 is its own parent: it is the root.
7	L14	op=1-2 child=1 top=2 components=4	1-2: parent[1] = 2: the root of the first element goes under the root of the second. 4 sets left.
8	L2	who=find(2) root=2	find(2): 2 is its own parent: it is the root.
9	L2	who=find(3) root=3	find(3): 3 is its own parent: it is the root.
10	L14	op=2-3 child=2 top=3 components=3	2-3: parent[2] = 3: the root of the first element goes under the root of the second. 3 sets left.
11	L2	who=find(3) root=3	find(3): 3 is its own parent: it is the root.
12	L2	who=find(4) root=4	find(4): 4 is its own parent: it is the root.
13	L14	op=3-4 child=3 top=4 components=2	3-4: parent[3] = 4: the root of the first element goes under the root of the second. 2 sets left.
14	L2	who=find(4) root=4	find(4): 4 is its own parent: it is the root.
15	L2	who=find(5) root=5	find(5): 5 is its own parent: it is the root.
16	L14	op=4-5 child=4 top=5 components=1	4-5: parent[4] = 5: the root of the first element goes under the root of the second. 1 set left.
17	L2	who=find(0) from=0 to=1 hops=1	find(0): 0 is not a root, follow parent[0] = 1.
18	L2	who=find(0) from=1 to=2 hops=2	find(0): 1 is not a root, follow parent[1] = 2.
19	L2	who=find(0) from=2 to=3 hops=3	find(0): 2 is not a root, follow parent[2] = 3.
20	L2	who=find(0) from=3 to=4 hops=4	find(0): 3 is not a root, follow parent[3] = 4.
21	L2	who=find(0) from=4 to=5 hops=5	find(0): 4 is not a root, follow parent[4] = 5.
22	L2	who=find(0) root=5 depth=5	find(0): the root is 5, 5 steps up.
23	L2	who=find(5) root=5	find(5): 5 is its own parent: it is the root.
24	L1	op=0?5 root of a=5 root of b=5 connected=true	0?5: the roots are 5 and 5, so 0 and 5 are connected.
25	L1	return=1 tallest tree=5 find hops=5 parent changes=0	1 set remains. The tallest tree has height 5, and all the finds together followed 5 parent links.

31.05.5

DSU on tree distinction

'DSU on tree' (also called Sack or small-to-large merging) is **not** the union-find data structure, even though the names are similar. It is a technique for answering questions about every subtree of a rooted tree, such as 'how many distinct colours are in each subtree?': keep a set per node, and when merging a child's set into its parent's, always merge the smaller set into the larger. Each element moves O(log n) times, because every move at least doubles its set, so the total is O(n log n) set operations.

The two ideas share the **merge the smaller into the larger** argument, but they solve different problems: union-find maintains a partition under merges and answers connectivity; DSU on tree answers per-subtree aggregates on a fixed tree. The function below counts distinct colours per subtree of a tree given by a parent array with parent[i] < i, processing nodes from the highest index down so every child is merged before its parent is.

Java

1static int[] distinctColours(int[] parent, int[] color) {         // parent[0] = -1, parent[i] < i
2    int n = parent.length;
3    List<Set<Integer>> sets = new ArrayList<>();
4    for (int i = 0; i < n; i++) { Set<Integer> s = new HashSet<>(); s.add(color[i]); sets.add(s); }
5    int[] answer = new int[n];
6    for (int v = n - 1; v >= 0; v--) {
7        answer[v] = sets.get(v).size();          // all children of v have been merged into it already
8        if (v == 0) break;
9        int p = parent[v];
10        Set<Integer> small = sets.get(v), large = sets.get(p);
11        if (small.size() > large.size()) { Set<Integer> t = small; small = large; large = t; }   // merge the smaller into the larger
12        large.addAll(small);
13        sets.set(p, large);
14    }
15    return answer;
16}

Practice ladder

Now try it yourself

Easy

Is Graph Bipartite?

Medium

Possible Bipartition
Evaluate Division
Satisfiability of Equality Equations

Advanced

Dynamic Connectivity (offline, rollback)
Number of Distinct Colors in Subtree (small-to-large)
Minimum Cost to Make Graph Connected with Constraints

Key takeaways

Rollback DSU: union by size without compression, plus a stack of changes to undo.
Parity and weighted DSUs store a relation to the parent on every link and combine it along the path.
Metadata lives at the root; DSU on tree is small-to-large merging on subtrees, a different technique.