icpc南昌2019 A.9102

题意是维护一个带删除操作的可持久化并查集，但不会实现，于是看题解考虑离线操作，解决完一个儿子就回溯操作

注意到离线仍需要带删除操作的并查集，所以需要虚根来实现

一开始操作数组开大了N*30爆MLE，后来因为答案要求的是Yes和No，而打的是YES和NO给了几发WA

const int N = 1e6 + 86;
int fa[N * 2], flag[N], sz[N * 2], tot, n, m, ans[N], dp[N * 2];
vi v[N];
struct NODE
{
    int op, a, b;
} e[N];

int find(int x)
{
    if (x == fa[x])
        return x;
    else
        return find(fa[x]);
}

void dfs(int i)
{
    for (auto it : v[i])
    {
        int op = e[it].op;
        if (op == 4)
        {
            int a = e[it].a, b = e[it].b;
            if (flag[a] == -1 || flag[b] == -1)
            {
                ans[it] = 0;
                dfs(it);
                continue;
            }
            int oa = find(flag[a]), ob = find(flag[b]);
            if (oa == ob)
                ans[it] = 1;
            else
                ans[it] = 0;
            dfs(it);
        }
        if (op == 5)
        {
            if (flag[e[it].a] == -1)
            {
                ans[it] = 0;
                dfs(it);
                continue;
            }
            int oa = find(flag[e[it].a]);
            ans[it] = sz[oa];
            dfs(it);
        }
        if (op == 1)
        {
            int a = e[it].a, b = e[it].b;
            if (flag[a] == -1 || flag[b] == -1)
            {
                dfs(it);
                continue;
            }
            int oa = find(flag[a]), ob = find(flag[b]), cap = 0;
            if(oa==ob){
                dfs(it);
                continue;
            }
            if(dp[oa] == dp[ob]){
                fa[ob] = oa; sz[oa] += sz[ob]; dp[oa]++;
                dfs(it);
                fa[ob] = ob; sz[oa] -= sz[ob]; dp[oa]--;
            }else{
                if(dp[oa] < dp[ob]) swap(oa, ob);
                fa[ob] = oa; sz[oa] += sz[ob];
                dfs(it);
                fa[ob] = ob; sz[oa] -= sz[ob];
            }
        }
        if (op == 2)
        {
            int a = e[it].a;
            if (flag[a]==-1){
                dfs(it);
                continue;
            }
            int oa=find(flag[a]),aa=flag[a];
            flag[a]=-1;
            sz[oa]--;
            dfs(it);
            sz[oa]++;
            flag[a]=aa;
        }
        if(op==3){
            int a = e[it].a, b = e[it].b;
            if (flag[a] == -1 || flag[b] == -1)
            {
                dfs(it);
                continue;
            }
            int oa = find(flag[a]), ob = find(flag[b]),aa=flag[a];
            if(oa==ob){
                dfs(it);
                continue;
            }
            sz[oa]--;
            sz[ob]++;
            flag[a]=++tot;
            sz[flag[a]]=1;
            fa[flag[a]]=ob;
            dfs(it);
            sz[oa]++;
            sz[ob]--;
            flag[a]=aa;
        }
    }
}

int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    tot = n + 1;
    int op, k, a, b=0;
    f(i, 1, n) flag[i] = fa[i] = i, sz[i] = 1;
    f(i, 1, m)
    {
        cin >> op >> k >> a;
        if (op != 2 && op != 5)
            cin >> b;
        v[k].pb(i);
        e[i] = (NODE){op, a, b};
    }
    dfs(0);
    f(i,1,m){
        if(e[i].op==4){
            if(ans[i])cout<<"Yes\n";
            else cout<<"No\n";
        }
        else if(e[i].op==5)cout<<ans[i]<<"\n";
    }
    return 0;
}