UVA11987 Almost Union-Find

题目描述

https://www.luogu.com.cn/problem/UVA11987

Solution

对于二操作，我们不需要真正的删除，而是新建一个节点，并将原来的点的值置零

注意到并查集如果只有合并的话是不需要考虑除了根节点以外的节点的值的

#include <iostream>
#include <cstdio>
#define maxn 100010
using namespace std;

int n, m;

int bl[2 * maxn], c1;

int fa[2 * maxn], sz[2 * maxn], sum[2 * maxn];
void init_fa() { for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1, sum[i] = i; }

inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } 

inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    fa[fx] = fy; sz[fy] += sz[fx]; sum[fy] += sum[fx];
} 

inline void solve_1() {
    int x, y; scanf("%d%d", &x, &y); 
    merge(bl[x], bl[y]);
}

inline void solve_2() { 
    int x, y, fx, fy, bx, by; scanf("%d%d", &x, &y); bx = bl[x]; by = bl[y];
    fx = find(bx); fy = find(by); if (fx == fy) return ;
    sz[fx]--; sum[fx] -= x; sum[fy] += x; sz[fy]++;
    bx = bl[x] = ++c1; fa[bx] = fy; 
}

inline void solve_3() {
    int x; scanf("%d", &x); printf("%d %d\n", sz[find(bl[x])], sum[find(bl[x])]);
}

int main() {
    cin >> n >> m; c1 = n; init_fa(); 
    for (int i = 1; i <= n; ++i) bl[i] = i;
    for (int i = 1; i <= m; ++i) {
        int opt; scanf("%d", &opt);
        switch (opt) {
        case 1 : solve_1(); break;
        case 2 : solve_2(); break;
        case 3 : solve_3(); break;
        }
    }
    return 0;
}