颜色平衡树 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 200000 + 100;
int n, f, ans;
int c[maxn], id[maxn], son[maxn], mxCnt[maxn];
vector<int> G[maxn];
map<int, int> cnt[maxn];
map<int, int>::iterator it;

int merge(int id1, int id2) {
    if (cnt[id1].size() > cnt[id2].size()) {
        swap(id1, id2);
    }
    for (it = cnt[id1].begin(); it != cnt[id1].end(); ++it) {
        cnt[id2][it->first] += it->second;
        mxCnt[id2] = max(mxCnt[id2], cnt[id2][it->first]);
    }
    return id2;
}

void dfs(int root) {
    int &idd = id[root];
    cnt[idd][c[root]] = 1;
    for (int pos : G[root]) {
        dfs(pos);
        idd = merge(idd, id[pos]);
        son[root] += son[pos];
    }
    if ((LL) mxCnt[idd] * cnt[idd].size() == son[root]) {
        ++ans;
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> c[i] >> f;
        G[f].push_back(i);
        id[i] = i;
        mxCnt[i] = 1;
        son[i] = 1;
    }
    dfs(1);
    cout << ans << endl;

    return 0;
}