记录编号	611288	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[USACO26 JAN G]COW Traversals	最终得分	100
用户昵称	hsl_beat	是否通过	通过
代码语言	C++	运行时间	5.462 s
提交时间	2026-01-25 13:27:28	内存使用	22.32 MiB

#include<bits/stdc++.h>
using namespace std;
struct DSU
{
    int _n;
    vector<int> _fa, _size;
    explicit DSU(int __n) : _n(__n) {
        _fa.resize(_n + 1);
        _size.resize(_n + 1);
        for (int i = 1; i <= _n; i++) {
            _fa[i] = i;
            _size[i] = 1;
        }
    }
    int find(int _x) {
        if (_fa[_x] == _x) {
            return _x;
        }
        return _fa[_x] = find(_fa[_x]);
    }
    int size(int _x) {
        return _size[_x] = _size[find(_x)];
    }
    void merge(int _x, int _y) {
        assert(1 <= _x && _x <= _n);
        assert(1 <= _y && _y <= _n);
        _x = find(_x);
        _y = find(_y);
        if (_x == _y) {
            return;
        }
        // if (_size[_x] < _size[_y]) {
        //     swap(_x, _y);
        // }
        _fa[_x] = _y;
        _size[_y] += _size[_x];  
    }
    bool same(int _x, int _y) {
        assert(1 <= _x && _x <= _n);
        assert(1 <= _y && _y <= _n);
        _x = find(_x);
        _y = find(_y);
        return _x == _y;
    }
};
int n, m;
int fa[500005];
signed main()
{
    freopen("COW.in", "r", stdin);
    freopen("COW.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> fa[i];
    }
    vector<vector<int>> a(n + 1);
    vector<pair<int, int>> e;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int idx;
        cin >> idx;
        char ch;
        cin >> ch;
        a[idx].push_back((ch == 'C' ? 0 : (ch == 'O' ? 1 : 2)));
        e.push_back({idx, (ch == 'C' ? 0 : (ch == 'O' ? 1 : 2))});
    }
    vector<vector<int>> ans(m, vector<int>(3, 0));
    DSU dsu(n);
    for (int i = 1; i <= n; i++) {
        if (!a[i].size()) {
            dsu.merge(i, fa[i]);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i].size()) {
            ans[m - 1][a[i].back()] += dsu.size(i);
        }
    }
    for (int i = m - 1; i >= 1; i--) {
        ans[i - 1] = ans[i];
        ans[i - 1][a[e[i].first].back()] -= dsu.size(e[i].first);
        a[e[i].first].pop_back();
        if (a[e[i].first].empty()) {
            int tp = dsu.size(e[i].first);
            dsu.merge(e[i].first, fa[e[i].first]);
            if (a[dsu.find(e[i].first)].size()) {
                ans[i - 1][a[dsu.find(fa[e[i].first])].back()] += tp;
            }
        } else {
            ans[i - 1][a[e[i].first].back()] += dsu.size(e[i].first);
        }
    }
    for (int i = 0; i < m; i++) {
        cout << ans[i][0] << ' ' << ans[i][1] << ' ' << ans[i][2] << '\n';
    }
    return 0;
}