题解：P14980 [USACO26JAN1] COW Traversals G
Hsl_Beat
·
·
题解
题意
举办的派对有 $3$ 种类型，在每一天晚上都会有一只猫娘举办了某种类型的派对，这只猫娘会一直举行下去直到自己换类型，问每天晚上这三种类型的派对都几只猫娘参加。
## 思路
首先把猫 $i$ 与自己的朋友连一条有向边，那么整张图就是一个内向基环树。每当一只猫娘举行了派对，这个结点相当于把自己和父亲结点的连边断开了，我们就需要统计每个举办派对的结点子树大小。
如果我们直接对着每一天的修改一个一个做，那么要处理分裂的问题，也能做但是不是很好写，所以我们考虑倒着做。
具体来说，每一天把当前猫娘举办的派对的答案回溯到这只猫娘举办的上一个派对那里（因为这只猫娘从上一个派对到举行当前派对这段时间一直都没变），但是如果这是这只猫娘举办的第一个派对了，那么来她排队里的猫娘和她自己都会跟随她的父亲结点，相当于连上了一条边，可以直接用 dsu 做，假如当前父亲节点追随的结点举办了派对，那么我们需要把当前结点子树的大小统计进这个派对的类型中。
差点忘了，我们既然从后往前做了，那需要初始化每种类型在最后时刻的人数，可以直接把一直都没举行派对的猫娘直接和她们的父亲节点连起来，然后对于有派对的把对应类型类加上自己子树的大小，然后从后往前一步一步更新当前答案这题做完了。
有一个注意的点在于并查集合并方向要写对，不然只能得 $4$ pts（也可能是我写法问题）。
这题洛谷评蓝是不是太夸张了（
```cpp
#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()
{
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;
}
```