[LCT刷题][边双缩点] P2542 [AHOI2005] 航线规划

题目思路

首先将删边操作转化为离线逆序加边操作。

考虑使用LCT+并查集维护边双缩点，对于每次连接的两个点检查是否位于同一连通块，如果不同则连边，否则就进入缩点，将$u\to v$的路径$split(u,v)$出来然后$dfs(v)$递归并查集合并并清空点，然后用并查集的祖先点作为缩点后的点连接到$v$的父亲上。以此来维护边双缩点。

需要注意的是，在LCT中的所有获取祖先操作都要套并查集的祖先查询，否则查到的不一定是真实的父亲(因为点可能已经被缩进边双了)。

缩点的过程类似这样…

实际上LCT上不连父亲边也没关系，因为LCT上寻找父亲依赖并查集，而并查集维护了父亲信息。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

struct UnionFind {
    std::vector<int> par, rank, size;
    int c;
    UnionFind(int n) : par(n), rank(n, 0), size(n, 1), c(n) {
        for(int i = 0; i < n; ++i) par[i] = i;
    }
    int find(int i) { return (par[i] == i ? i : (par[i] = find(par[i]))); }
    void merge(int u, int v) {
        int ufa = find(u), vfa = find(v);
        if(ufa != vfa) par[ufa] = vfa;
    }
};

UnionFind uf(1);

namespace LCT{
    int ch[N][2], f[N], tag[N], siz[N];

    #define ls ch[x][0]
    #define rs ch[x][1]

    inline void push_reverse(int x) { swap(ls, rs), tag[x] ^= 1; }

    inline void push_down(int x) {
        if(tag[x]) {
            if(ls) push_reverse(ls);
            if(rs) push_reverse(rs);
            tag[x] = 0;
        }
    }

    void cleanch(int x) { ch[x][0] = ch[x][1] = f[x] = tag[x] = siz[x] = 0; }

    inline void push_up(int x) { cleanch(0), siz[x] = siz[ls] + siz[rs] + 1; }

    #define get(x) (ch[uf.find(f[x])][1] == x)                        
    #define isRoot(x) (ch[uf.find(f[x])][0] != x && ch[uf.find(f[x])][1] != x)

    void rotate(int x) {
        int y = uf.find(f[x]), z = uf.find(f[y]), k = get(x);
        if(!isRoot(y)) ch[z][ch[z][1] == y] = x;
        ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
        ch[x][!k] = y, f[y] = x, f[x] = z;
        push_up(y); push_up(x);
    }

    void update(int x) {
        if(!isRoot(x)) update(uf.find(f[x]));
        push_down(x);
    }

    void splay(int x) {
        update(x);
        for(int fa = uf.find(f[x]); !isRoot(x); rotate(x), fa = uf.find(f[x])) {
            if(!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);
        }
        push_up(x);
    }

    int access(int x) {
        int p;
        for(p = 0; x; x = uf.find(f[p = x])) splay(x), rs = p, push_up(x);
        return p;
    }

    void makeRoot(int x) { access(x), splay(x), push_reverse(x); }

    int findRoot(int x) {
        access(x), splay(x);
        while(ch[x][0]) push_down(x), x = ch[x][0];
        splay(x);
        return x;
    }

    void split(int x, int y) {
        makeRoot(x);
        access(y), splay(y);
    }

    void link(int x, int y) { makeRoot(x); if(findRoot(y) != x) f[x] = y; }
}

#define pii pair<int, int>
#define fir first
#define sec second
vector<int> g[N];
map<pii, int> mp;

struct query{
    int op, u, v;
}q[N];

vector<int> ans;

void merge_link(int u){
    LCT::push_down(u);
    if(LCT::ch[u][0]) merge_link(LCT::ch[u][0]), uf.merge(LCT::ch[u][0], u);
    if(LCT::ch[u][1]) merge_link(LCT::ch[u][1]), uf.merge(LCT::ch[u][1], u);
    LCT::cleanch(u);
}

inline void solve(){
    int n = 0, m = 0; cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        mp[{u, v}] = mp[{v, u}] = 1;
    }
    uf = UnionFind(n + 5);
    int op_cnt = 0;
    while(cin >> q[++op_cnt].op) {
        if(q[op_cnt].op == -1) { op_cnt -= 1; break; }
        int opu, opv; cin >> opu >> opv;
        q[op_cnt].u = opu, q[op_cnt].v = opv;
        if(!q[op_cnt].op) mp[{opu, opv}] = mp[{opv, opu}] = 0;
    }
    reverse(q + 1, q + 1 + op_cnt);
    for(auto &[edge, state] : mp) {
        if(!state) continue;
        mp[{edge.sec, edge.fir}] = 0;
        int ufa = uf.find(edge.fir), vfa = uf.find(edge.sec);
        if(LCT::findRoot(ufa) != LCT::findRoot(vfa)) LCT::link(ufa, vfa);
        else {
            if(ufa == vfa) continue;
            LCT::split(ufa, vfa);
            merge_link(vfa);
            int block = uf.find(vfa);
            LCT::f[block] = uf.find(LCT::f[vfa]);
            LCT::cleanch(block);
            LCT::push_up(block);
        }
    }
    for(int i = 1; i <= op_cnt; i++) {
        int ufa = uf.find(q[i].u), vfa = uf.find(q[i].v);
        LCT::split(ufa, vfa);
        if(q[i].op == 0) {
            merge_link(vfa);
            int block = uf.find(vfa);
            LCT::f[block] = LCT::f[vfa];
            LCT::cleanch(block);
            LCT::push_up(block);
        } else {
            ans.emplace_back(LCT::siz[vfa] - 1);
        }
    }
    reverse(ans.begin(), ans.end());
    for(auto v : ans) cout << v << endl;

}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165