首先说一下，$Dfs$序上跑莫队是十分巧妙的做法，与树上莫队如出一辙。
但是在这个题里莫队比较慢，亲测花了$5000+ms$。
这里提供一个不一样的思路，快了整整$4$倍。

做树上启发式合并，先用桶暴力维护每种颜色出现的次数，再对桶里的颜色个数再次计数，最后统计每种颜色出现次数是否一致。
这样讲比较抽象，这里讲详细一点：
设$cnt[x]$表示颜色$x$出现次数，$f[i]$表示$cnt[x] == i$的$i$的个数，若统计到$u$的子树，判断时只需判断$f[cnt[c[u]]] * cnt[c[u]] == sz[u]$即可，非常方便，复杂度也相当优秀，达到了$O(n\log_2n)$

啥，不了解树上启发式合并？
实质上就是优化暴力，在暴力统计的时候继承重儿子的贡献，暴力收集轻儿子信息，是$O(n\log_2n)$的。
因为重链剖分后，每个节点$u$只会在$u$到根的路径上轻边处被暴力统计，而到根的路径上轻边数量是$O(\log n)$的，所以每个点的贡献不超过$(\log n)$级别，总体上是线性对数，非常快，常数也小。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const lucky[6] = "H8281";
const int N = 2e5 + 20, M = N * 2;

int n, m, a[N], ans;
int f[N], g[N];
int idx, to[M], nxt[M], h[N], sz[N], son[N];

void add(int u, int v)
{
    idx ++; to[idx] = v; nxt[idx] = h[u]; h[u] = idx;
}

void Dfs1(int u, int pa)
{
    int v;
    sz[u] = 1;
    for(int i = h[u]; i ; i = nxt[i])
    {
        v = to[i];
        if(v == pa) continue;
        Dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}

void Clear(int u, int pa)
{
    int v;
    g[f[a[u]]] = 0;
    f[a[u]] = 0;
    for(int i = h[u]; i ; i = nxt[i])
    {
        v = to[i];
        if(v == pa) continue;
        Clear(v, u);
    }
}

void collect(int u, int pa)
{
    int v;
    f[a[u]] ++;
    g[f[a[u]] - 1] --;
    g[f[a[u]]] ++;
    for(int i = h[u]; i ; i = nxt[i])
    {
        v = to[i];
        if(v == pa) continue;
        collect(v, u);
    }
}

void Dfs2(int u, int pa)
{
    int v;
    for(int i = h[u]; i ; i = nxt[i])
    {
        v = to[i];
        if(v == pa || v == son[u]) continue;
        Dfs2(v, u);
        Clear(v, u);
    }
    if(son[u]) Dfs2(son[u], u);
    f[a[u]] ++; g[f[a[u]]] ++; g[f[a[u]] - 1] --;
    for(int i = h[u]; i ; i = nxt[i])
    {
        v = to[i];
        if(v == pa || v == son[u]) continue;
        collect(v, u);
    }
    if(1ll * g[f[a[u]]] * f[a[u]] == sz[u]) ans ++;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        int C, F;
        scanf("%d%d", &C, &F);
        a[i] = C; if(F) add(F, i), add(i, F);
    }
    Dfs1(1, 0);
    Dfs2(1, 0);
    printf("%d\n", ans);
    return 0;
}