f.cpp

#include <bits/stdc++.h>

using namespace std;
vector <int> vec;
int timer = 0;
void dfs(int x){
    tin[x] = timer++;
    vec.pb(x);
    a.pb(color[x]);
    was[x] = 1;
    for (int i = 0; i < g[x].size(); i++){
        int to = g[x][i];
        if (!was[to]){
            dfs(to);
        }
    }

    tout[x] = timer++;
    a.pb(0);
    vec.pb(x);
}

void add(int x){
    if (a[x] != 0){
        cnt[a[x]]++;
        cnt2[cnt[a[x]]]++;
    }
}
void del(int x){
    if (a[x] != 0){
        cnt[a[x]]--;
        cnt2[cnt[a[x]]]--;
    }
}

int main()
{
    ...


    dfs(1);
    len = sqrt(2 * n);
    pair <pair <int, int>, pair <int, pair <int, int> > > b[q];
    for (int i = 0; i < q; i++){
        cin >> v >> k;
        l = tin[v];
        r = tout[v];
        b[i].first.first = l / len;
        b[i].first.second = r;
        b[i].second.first = l;
        b[i].second.second.first = k;
        b[i].second.second.second = i;
    }
    sort(b, b + q);
    left = 0;
    right = -1;
    for (int i = 0; i < q; i++){
        int l = b[i].second.first;
        int r = b[i].first.second;
        int k = b[i].second.second.first;
        int ind = b[i].second.second.second;

        while (right < r){
            right++;
            add(right);
        }
        while (left > l){
            left--;
            add(left);
        }

        while (right > r){
            del(right);
            right--;
        }
        while (left < l){
            del(left);
            left++;
        }
        ans[ind] = cnt2[k];
    }

    for (int i = 0; i < q; i++){
        cout << ans[i] << ' ';
    }
    return 0;
}