Persistent DSU (offline)

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

struct edge {
    int op;
    int to;
    edge *next;
};

const int N = 100010;
edge *g[N];
int freep;

int type[N];
int a[N];
int b[N];
int ans[N];

int dsu[N];
int rnk[N];

int find_root(int x) {
    while (dsu[x] != x)
        x = dsu[x];
    return x;
}

vector<int> st;

void unite(int a, int b) {
    a = find_root(a);
    b = find_root(b);
    if (a == b) {
        st.push_back(-1);
        return;
    }
    if (rnk[a] < rnk[b]) {
        swap(a, b);
    }
    dsu[b] = a;
    rnk[a] += rnk[b];
    st.push_back(b);
}

void dfs(int v) {
    for (edge *e = g[v]; e; e = e->next) {
        int o = e->op;
        if (type[e->op] == 1) {
            unite(a[o], b[o]);
        } else {
            ans[e->op] = (find_root(a[o]) == find_root(b[o]));
        }
        dfs(e->to);
        if (type[o] == 1) {
            int curV = st.back();
            st.pop_back();
            if (curV != -1) {
                int p = dsu[curV];
                rnk[p] -= rnk[curV];
                dsu[curV] = curV;
            }
        }
    }
}

int main() {
    int n, m;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i <= n; ++i)
        dsu[i] = i;
    for (int i = 0; i < m; ++i) {
        char tp;
        int old;
        cin >> tp >> old >> a[i] >> b[i];
        type[i] = (tp == '+');
        edge * e = new edge;
        e->op = i;
        e->to = i + 1;
        e->next = g[old];
        g[old] = e;
    }
    dfs(0);
    for (int i = 0; i < m; ++i)
        if (!type[i])
            cout << (ans[i]? "YES" : "NO") << '\n';
}