struct DSU {
    vector<int> pa, sz;   // sz[i] = total nodes in tree rooted at i
    int groups;           // current number of connected components
    
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1), groups(n) {
        iota(pa.begin(), pa.end(), 0);  // pa[i] = i
    }
    
    // Find root with path compression
    int find(int x) {
        return pa[x] == x ? x : pa[x] = find(pa[x]);
    }
    
    // Union by size; returns true if they were in different sets (merge happened)
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;       // already in same set
        if (sz[x] < sz[y]) swap(x, y); // x is the larger tree
        pa[y] = x;                      // attach small tree under large tree
        sz[x] += sz[y];
        groups--;
        return true;
    }
    
    // Check if connected
    bool connected(int x, int y) { return find(x) == find(y); }
    
    // Size of the component containing x
    int size(int x) { return sz[find(x)]; }
};

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    int groups;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1), groups(n) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y]; groups--;
        return true;
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    int n, q;
    cin >> n >> q;
    DSU dsu(n);
    
    while (q--) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) {
            // Add link
            if (dsu.unite(a, b))
                cout << "New link: " << a << " - " << b << "\n";
            else
                cout << "Already connected, no new link needed\n";
        } else {
            // Query
            cout << (dsu.connected(a, b) ? "Can communicate" : "Cannot communicate") << "\n";
        }
    }
    return 0;
}

We have: dist[x] = height[x] - height[rx]
         dist[y] = height[y] - height[ry]

If we attach ry under rx, we need dist[ry] to satisfy:
    height[ry] - height[rx] = ?
    
From height[y] - height[x] = d:
    (dist[y] + height[ry]) - (dist[x] + height[rx]) = d
    height[ry] - height[rx] = d + dist[x] - dist[y]

Therefore dist[ry] = d + dist[x] - dist[y]

// Complete Weighted Union-Find
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int pa[MAXN], sz_arr[MAXN];
long long dist[MAXN];  // dist[x] = height[x] - height[find(x)]

void init(int n) {
    for (int i = 1; i <= n; i++) { pa[i] = i; sz_arr[i] = 1; dist[i] = 0; }
}

int find(int x) {
    if (pa[x] == x) return x;
    int root = find(pa[x]);
    dist[x] += dist[pa[x]];
    pa[x] = root;
    return root;
}

// Declare height[y] - height[x] = d
// Returns true = no contradiction; false = contradicts known info
bool add_info(int x, int y, long long d) {
    int rx = find(x), ry = find(y);
    long long dx = dist[x], dy = dist[y];
    
    if (rx == ry) {
        // Already in same set, verify no contradiction
        return (dy - dx == d);
    }
    
    // Merge: attach small tree under large tree
    if (sz_arr[rx] < sz_arr[ry]) {
        swap(rx, ry); swap(dx, dy); d = -d;
    }
    pa[ry] = rx;
    dist[ry] = d + dx - dy;
    sz_arr[rx] += sz_arr[ry];
    return true;
}

long long query(int x, int y) {
    find(x); find(y);
    return dist[y] - dist[x];  // height[y] - height[x]
}

int main() {
    int n = 5;
    init(n);
    
    add_info(1, 2, 3);   // height[2] - height[1] = 3 (2 is 3cm taller than 1)
    add_info(2, 3, 5);   // height[3] - height[2] = 5
    
    // Query difference between 1 and 3
    cout << "3 is " << query(1, 3) << " cm taller than 1\n";  // outputs 8
    
    // Add contradictory info
    cout << (add_info(1, 3, 10) ? "Consistent" : "Contradiction") << "\n";  // Contradiction (should be 8)
    cout << (add_info(1, 3, 8)  ? "Consistent" : "Contradiction") << "\n";  // Consistent
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 150005;
int pa[MAXN * 3], sz[MAXN * 3];

void init(int n) {
    for (int i = 0; i < 3 * (n + 1); i++) { pa[i] = i; sz[i] = 1; }
}
int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
bool same(int x, int y) { return find(x) == find(y); }
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    pa[y] = x; sz[x] += sz[y];
}

int main() {
    int n, k;
    cin >> n >> k;
    init(n);
    
    int lies = 0;
    while (k--) {
        int t, x, y;
        cin >> t >> x >> y;
        
        // Out-of-range numbers are immediately lies
        if (x < 1 || x > n || y < 1 || y > n) { lies++; continue; }
        
        if (t == 1) {
            // Declare x and y are the same type
            if (same(x, y + n) || same(x, y + 2 * n)) {
                lies++;  // contradiction: x and y have predator-prey relationship
            } else {
                unite(x, y);
                unite(x + n, y + n);
                unite(x + 2 * n, y + 2 * n);
            }
        } else {
            // Declare x eats y
            if (x == y) { lies++; continue; }  // cannot eat itself
            if (same(x, y) || same(x, y + n)) {
                lies++;  // contradiction
            } else {
                unite(x + n, y);
                unite(x + 2 * n, y + n);
                unite(x, y + 2 * n);
            }
        }
    }
    
    cout << lies << "\n";
    return 0;
}

Idea: Each time we merge, if the two people were not in the same set (unite returns true), decrement component count by 1. Final dsu.groups is the answer.

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    int groups;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1), groups(n) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y]; groups--;
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    while (m--) {
        int a, b; cin >> a >> b;
        dsu.unite(a, b);
    }
    cout << dsu.groups << "\n";
    return 0;
}

Trace (N=5, M=3):

Initial groups = 5
unite(1,2) → different sets, groups = 4, pa[2]=1
unite(2,3) → different sets, groups = 3, pa[3]=1
unite(4,5) → different sets, groups = 2, pa[5]=4
Output: 2 ✓

Idea: When adding edge (u, v), if u and v are already connected (find(u)==find(v)), this edge creates a cycle.

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;  // already connected = adding edge creates cycle
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    bool has_cycle = false;
    while (m--) {
        int u, v; cin >> u >> v;
        if (!dsu.unite(u, v)) has_cycle = true;
    }
    cout << (has_cycle ? "YES" : "NO") << "\n";
    return 0;
}

Key point: unite returning false means both endpoints are already connected → this edge is redundant → cycle exists.

Idea: Use Union-Find with sz[]. After all merges, iterate all nodes and find the maximum sz[find(i)].

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
    }
    int size(int x) { return sz[find(x)]; }
};

int main() {
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    while (m--) {
        int u, v; cin >> u >> v;
        dsu.unite(u, v);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dsu.size(i));
    cout << ans << "\n";
    return 0;
}

Idea: Kruskal's algorithm: sort all edges by weight ascending, try to add each one. If both endpoints are in different sets (no cycle), add to MST. If MST has N-1 edges at the end, the graph is connected.

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
        return true;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<tuple<int,int,int>> edges(m);
    for (auto& [w, u, v] : edges) cin >> u >> v >> w;
    sort(edges.begin(), edges.end());  // sort by weight
    
    DSU dsu(n);
    long long total = 0;
    int cnt = 0;  // edges in MST
    
    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) {
            total += w;
            cnt++;
            if (cnt == n - 1) break;  // found n-1 edges
        }
    }
    
    cout << (cnt == n - 1 ? total : -1LL) << "\n";
    return 0;
}

Trace example (N=4, edges: 1-2 w=1, 2-3 w=2, 1-3 w=3, 3-4 w=4):

Sorted: (1,1,2), (2,2,3), (3,1,3), (4,3,4)

Add edge(1,2) w=1 → unite succeeds, cnt=1, total=1
Add edge(2,3) w=2 → unite succeeds, cnt=2, total=3
Add edge(1,3) w=3 → find(1)=find(3), already connected, skip
Add edge(3,4) w=4 → unite succeeds, cnt=3=n-1, total=7

Output: 7

Core idea:

1. Record all operations
2. Process from back to front: block becomes connect; forward connect operations that occur before a block need to be excluded
3. Use Union-Find + offline reverse processing, output query results in reverse

Here's a simplified version using offline reverse + operation recovery (assuming each pair of servers is disconnected at most once):

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
        return true;
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<tuple<int,int,int>> ops(m);  // {type, a, b}, type: 0=connect,1=query,2=block
    set<pair<int,int>> blocked;         // blocked edges
    
    for (auto& [t, a, b] : ops) {
        string op; cin >> op >> a >> b;
        if (op == "connect") t = 0;
        else if (op == "query") t = 1;
        else { t = 2; blocked.insert({min(a,b), max(a,b)}); }
    }
    
    // Process in reverse
    DSU dsu(n);
    // First add all edges that exist in the "final state" (connect but not blocked)
    for (auto& [t, a, b] : ops) {
        if (t == 0) {
            auto key = make_pair(min(a,b), max(a,b));
            if (!blocked.count(key)) dsu.unite(a, b);
        }
    }
    
    vector<string> answers;
    for (int i = m - 1; i >= 0; i--) {
        auto [t, a, b] = ops[i];
        if (t == 2) {
            // In reverse, block becomes connect
            dsu.unite(a, b);
        } else if (t == 1) {
            answers.push_back(dsu.connected(a, b) ? "YES" : "NO");
        }
        // connect operations are not processed in reverse (already added during init)
    }
    
    reverse(answers.begin(), answers.end());
    for (auto& s : answers) cout << s << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int pa[MAXN], sz_arr[MAXN];
long long dist[MAXN];

void init(int n) {
    for (int i = 1; i <= n; i++) { pa[i] = i; sz_arr[i] = 1; dist[i] = 0; }
}

int find(int x) {
    if (pa[x] == x) return x;
    int root = find(pa[x]);
    dist[x] += dist[pa[x]];
    pa[x] = root;
    return root;
}

// Declare height[b] - height[a] = d, returns false if contradiction
bool add_info(int a, int b, long long d) {
    int ra = find(a), rb = find(b);
    long long da = dist[a], db = dist[b];
    if (ra == rb) return (db - da == d);
    if (sz_arr[ra] < sz_arr[rb]) { swap(ra, rb); swap(da, db); d = -d; }
    pa[rb] = ra;
    dist[rb] = d + da - db;
    sz_arr[ra] += sz_arr[rb];
    return true;
}

int main() {
    int n, m, q;
    cin >> n >> m;
    init(n);
    
    bool global_conflict = false;
    for (int i = 0; i < m; i++) {
        int a, b; long long d;
        cin >> a >> b >> d;
        if (!add_info(a, b, d)) global_conflict = true;
    }
    
    cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        int ra = find(a), rb = find(b);
        if (ra != rb) cout << "unknown\n";
        else if (global_conflict) cout << "conflict\n";
        else cout << dist[b] - dist[a] << "\n";
    }
    return 0;
}

Sample input:

5 3
1 2 3    → height[2] - height[1] = 3
2 3 5    → height[3] - height[2] = 5
1 3 8    → height[3] - height[1] = 8 (consistent with above)

2
1 3      → output 8
1 4      → output unknown

Use weighted Union-Find where dist[x] records parity (0=not flipped, 1=flipped odd number of times):

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
int pa[MAXN];
int flip[MAXN];  // flip[x] = parity of flips of x relative to root

void init(int n) {
    for (int i = 0; i <= n; i++) { pa[i] = i; flip[i] = 0; }
}

int find(int x) {
    if (pa[x] == x) return x;
    int root = find(pa[x]);
    flip[x] ^= flip[pa[x]];  // XOR accumulate parity along path
    pa[x] = root;
    return root;
}

// Declare "x and y are in the same group with flip relation d (0=same color, 1=different color)"
void unite(int x, int y, int d) {
    int rx = find(x), ry = find(y);
    int fx = flip[x], fy = flip[y];
    if (rx == ry) return;
    pa[ry] = rx;
    flip[ry] = d ^ fx ^ fy;
}

// Query color offset of x relative to root
int query(int x) {
    find(x);
    return flip[x];
}

This template applies to all "parity relationship" type bipartite Union-Find problems.

This is a standard Union-Find template problem:

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> pa, sz;
    explicit DSU(int n) : pa(n + 1), sz(n + 1, 1) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        pa[y] = x; sz[x] += sz[y];
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) dsu.unite(x, y);
        else cout << (dsu.connected(x, y) ? "Y" : "N") << "\n";
    }
    return 0;
}

Use the "Bipartite Union-Find" code from Section 5.6.8 directly. Key details:

• Eating itself (x == y and type=2): lie
• Out-of-range number (x > n or y > n): lie
• Contradiction check before merge

// Use the code from Section 5.6.8 directly
// Key test cases:
// N=100, K=7
// 1 101 1    → x=101 > N=100, lie, lies=1
// 2 1 2      → declare 1 eats 2, no contradiction, merge
// 2 2 3      → declare 2 eats 3, no contradiction, merge
// 2 3 1      → 1 eats 2 eats 3 eats 1 ← valid cycle
// 1 1 3      → 1 and 3 same type? But 1 eats 3, contradiction, lies=2
// 2 3 3      → x==y, eating itself, lies=3
// 1 1 2      → 1 and 2 same type? But 1 eats 2, contradiction, lies=4
// Output: 4

Complete code is in Section 5.6.8, submit directly.

Why no path compression? Path compression changes the tree structure; after rollback the structure would be corrupted. Use only union by rank (tree height O(log N)), each find takes at most O(log N) steps, which is acceptable.

// Persistent Union-Find framework (using persistent segment tree to maintain pa[])
// Each unite operation only modifies 2 nodes (rx and ry),
// making a point update on the segment tree to generate a new version

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXLOG = 20;

struct Node {
    int left, right, val, rnk;  // rnk = rank of tree
} tr[MAXN * MAXLOG * 4];

int root[MAXN], cnt = 0;  // root[i] = root node of version i

// Build initial segment tree (all nodes pa[i] = i)
int build(int l, int r) {
    int node = ++cnt;
    if (l == r) {
        tr[node].val = l;  // pa[l] = l (itself is root)
        tr[node].rnk = 0;
        return node;
    }
    int mid = (l + r) / 2;
    tr[node].left = build(l, mid);
    tr[node].right = build(mid + 1, r);
    return node;
}

// Persistent point update: pa[pos] = new_val
int update(int prev, int l, int r, int pos, int new_val, int new_rnk = -1) {
    int node = ++cnt;
    tr[node] = tr[prev];  // copy previous version
    if (l == r) {
        tr[node].val = new_val;
        if (new_rnk >= 0) tr[node].rnk = new_rnk;
        return node;
    }
    int mid = (l + r) / 2;
    if (pos <= mid)
        tr[node].left = update(tr[prev].left, l, mid, pos, new_val, new_rnk);
    else
        tr[node].right = update(tr[prev].right, mid + 1, r, pos, new_val, new_rnk);
    return node;
}

// Query pa[pos]
int query(int node, int l, int r, int pos) {
    if (l == r) return tr[node].val;
    int mid = (l + r) / 2;
    if (pos <= mid) return query(tr[node].left, l, mid, pos);
    return query(tr[node].right, mid + 1, r, pos);
}

int n;

// Find root of x in version ver (no path compression!)
int find(int ver, int x) {
    int p = query(root[ver], 1, n, x);
    if (p == x) return x;
    return find(ver, p);
}

int main() {
    int m;
    cin >> n >> m;
    root[0] = build(1, n);
    
    for (int i = 1; i <= m; i++) {
        int op; cin >> op;
        if (op == 1) {
            // Merge
            int x, y; cin >> x >> y;
            int rx = find(i - 1, x), ry = find(i - 1, y);
            // ... union by rank, generate root[i]
        } else if (op == 2) {
            // Rollback to version k
            int k; cin >> k;
            root[i] = root[k];
        } else {
            // Query
            int x; cin >> x;
            cout << find(i - 1, x) << "\n";
            root[i] = root[i - 1];
        }
    }
    return 0;
}

Full implementation reference: Luogu P3402 Persistent Union-Find