f.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int INF = 1e9 + 1;
const int MAXN = 2e5 + 10;
int tin[MAXN], a[2 * MAXN], tout[MAXN], ans[MAXN], col[MAXN], cnt[MAXN], cntCnt[MAXN];
int n, m;
pair <pair <int, int>, pair <int, pair <int, int> > > b[MAXN];
int timer = 0;
bool was[MAXN];
vector <int> g[MAXN];

void dfs(int v){
    was[v] = 1;
    tin[v] = ++timer;
    a[tin[v]] = col[v];
    for (int to : g[v]){
        if (!was[to]){
            dfs(to);
        }
    }

    tout[v] = ++timer;
    a[tout[v]] = -1;
}

void add(int x){
    if (x == -1){
        return;
    }
    cnt[x]++;
    cntCnt[cnt[x]]++;
}

void del(int x){
    if (x == -1){
        return;
    }
    cntCnt[cnt[x]]--;
    cnt[x]--;
}

void solve(){

    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> col[i];
    }
    for (int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

    dfs(1);
    int len = sqrt(n);
    for (int i = 1; i <= m; i++){
        int v, k;
        cin >> v >> k;
        b[i].f.f = tin[v] / len;
        b[i].f.s = tout[v];
        b[i].s.f = tin[v];
        b[i].s.s.f = i;
        b[i].s.s.s = k;
    }

    sort(b + 1, b + m + 1);
    int l = 1;
    int r = 0;
    for (int i = 1; i <= m; i++){
        while (r < b[i].f.s){
            r++;
            add(a[r]);
        }
        while (l > b[i].s.f){
            l--;
            add(a[l]);
        }
        while (r > b[i].f.s){
            del(a[r]);
            r--;
        }
        while(l < b[i].s.f){
            del(a[l]);
            l++;
        }

        ans[b[i].s.s.f] = cntCnt[b[i].s.s.s];
    }

    for (int i = 1; i <= m; i++){
        cout << ans[i] << '\n';
    }

}
int main() {
    IOS;
    //freopen("rmq.in", "r", stdin);
    //freopen("rmq.out", "w", stdout);
    int t = 1;
   // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}