题目链接

Marked Ancestor Aizu - 2170

思路

$$ 这道并查集的题是好题\\\\这是一类问题，并查集的解决的是不断并然后查，这类问题是不断拆然后查\\\\我们可以离线操作，倒序回答，则迎刃而解。\\\\\\\\本题有几个注意事项\\\\1.fa[1]=1\\\\2.每个点可以mark多次，mark数组不能用布尔类型，可以记录标记最早时间或次数，笔者标记次数\\\\3.long long 程序设计竞赛没有int类型 lol $$

时间复杂度

$$ O(Qlog(N)) $$

代码

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;


const int MAXN = 1e5 + 10;
int mark[MAXN];
int fa[MAXN];
int a[MAXN];
char op[MAXN][5];

class DSU {
public:
    vector<int> p, r;

    void init(int n) {
        p.resize(n + 10);
        r.resize(n + 10);
        for (int i = 0; i <= n; i++) {
            p[i] = i;
            r[i] = 0;
        }
    }

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

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }


        p[x] = y;//new
        return true;// new

        if (r[x] < r[y]) {
            p[x] = y;
        } else {
            p[y] = x;
            if (r[x] == r[y]) {
                r[x]++;
            }
        }
        return true;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    DSU dsu;
    int n, q;
    fa[1] = 1;
    while (scanf("%d%d", &n, &q), n + q) {
        memset(mark, 0, sizeof mark);
        dsu.init(n);
        for (int i = 2; i <= n; i++) {
            int x;
            scanf("%d", &x);// don't forget &
            fa[i] = x;
        }
        for (int i = 1; i <= q; i++) {
            scanf("%s%d", op[i], &a[i]);
            if (op[i][0] == 'M') {
                mark[a[i]]++;
            }
        }
        for (int i = 2; i <= n; i++) {
            if (mark[i]) {
                continue;
            }
            dsu.unite(i, fa[i]);
        }
        long long ans = 0;
        for (int i = q; i >= 1; i--) {
            if (op[i][0] == 'M') {
                mark[a[i]]--;
                if (mark[a[i]] == 0) {
                    dsu.unite(a[i], fa[a[i]]);
                }
            } else {
                ans += dsu.find(a[i]);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}