「BZOJ 4998」星球联盟

题目大意：

先建出一棵树，预处理出 $dep$ 和 $fa$，然后用一个并查集维护连通性，另一个并查集维护每个点所在的环。缩环的时候每次向上跳 $father$，每跳一步就减少一个点，因此每个点最多被跳到一次，所以总复杂度是 $O((m+q)\log n)$ 的。

#include <cstdio>
 
const int N = 200005, M = 400005;
 
struct Node {
    int x, y;
} a[M];
 
int head[N], nxt[M], v[M], siz[N], f1[N], f2[N], fa[N], dep[N], tot;
 
int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void swap(int &x, int &y) {
    x ^= y, y ^= x, x ^= y;
}
void add(int from, int to) {
    nxt[++tot] = head[from];
    head[from] = tot, v[tot] = to;
}
int find1(int x) {
    if (x != f1[x]) f1[x] = find1(f1[x]);
    return f1[x];
}
int find2(int x) {
    if (x != f2[x]) f2[x] = find2(f2[x]);
    return f2[x];
}
void dfs(int u, int f, int d) {
    fa[u] = f, dep[u] = d;
    for (int i = head[u]; i; i = nxt[i])
        if (v[i] != f) dfs(v[i], u, d + 1);
}
void merge(int x, int y) {
    x = find2(x), y = find2(y);
    while (x != y) {
        if (dep[x] < dep[y]) swap(x, y);
        int fx = find2(fa[x]);
        f2[x] = fx, siz[fx] += siz[x], x = fx;
    }
}
 
int main() {
    int n = read(), m = read(), q = read();
    for (int i = 1; i <= n; ++i) f1[i] = i;
    for (int i = 1; i <= m + q; ++i) {
        int x = read(), y = read();
        int fx = find1(x), fy = find1(y);
        if (fx != fy) add(x, y), add(y, x), f1[fx] = fy;
        a[i] = (Node){x, y};
    }
    for (int i = 1; i <= n; ++i) if (!dep[i]) dfs(i, 0, 0);
    for (int i = 1; i <= n; ++i) f1[i] = f2[i] = i, siz[i] = 1;
    for (int i = 1; i <= m + q; ++i) {
        int fx = find1(a[i].x), fy = find1(a[i].y);
        if (fx != fy) {
            f1[fx] = fy;
            if (i > m) puts("No");
        } else {
            merge(a[i].x, a[i].y);
            if (i > m) printf("%d\n", siz[find2(a[i].x)]);
        }
    }
    return 0;
}

时间复杂度 $O((m+q)\log n)$