icpc南昌2019 A.9102

发表于 更新于 分类于 本文字数： 539 阅读时长 ≈ 2 分钟

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

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

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

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
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;
}