DSU on Tree - 375D Codeforces

//Make CSP great again
//You're as beautiful as the day I lost you
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 1e5;
vector<int> Adj[N + 1];
vector<pair<int, int> >  Query[N + 1];
int n, q, st[N + 1], ed[N + 1], timer, order[N + 1], a[N + 1], res[N + 1], cnt[N + 1];
struct FenwickTree
{
    int Tree[N + 1];
    FenwickTree()
    {
        memset(Tree, 0, sizeof(Tree));
    }
    void add(int pos, int val)
    {
        for (; pos <= N; pos += pos & (-pos))
        {
            Tree[pos] += val;
        }
    }
    int sum(int pos)
    {
        int ret = 0;
        for (; pos > 0; pos -= pos & (-pos))
        {
            ret += Tree[pos];
        }
        return ret;
    }
    int sum(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
};
FenwickTree Tree;
void Insert(int u)
{
    u = a[u];
    if (cnt[u])
    {
        Tree.add(cnt[u], -1);
    }
    ++cnt[u];
    Tree.add(cnt[u], 1);
}
void Del(int u)
{
    u = a[u];
    Tree.add(cnt[u], -1);
    --cnt[u];
    if (cnt[u])
    {
        Tree.add(cnt[u], 1);
    }
}
int sz(int u)
{
    return ed[u] - st[u] + 1;
}
int Get(int k)
{
    return Tree.sum(k, N);
}
void read()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
    }
    for (int i = 1; i < n; ++ i)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }
    for (int i = 1; i <= q; ++ i)
    {
        int u, k;
        cin >> u >> k;
        Query[u].push_back(make_pair(i, k));
    }
}
void DFS(int u, int p)
{
    ++timer;
    st[u] = timer;
    order[timer] = u;
    for (int v : Adj[u])
    {
        if (v == p)
        {
            continue;
        }
        DFS(v, u);
    }
    ed[u] = timer;
}
void processDFS(int u, int p)
{
    int bigChild = -1;
    for (int v : Adj[u])
    {
        if (v == p)
        {
            continue;
        }
        if (bigChild == -1 || sz(v) > sz(bigChild))
        {
            bigChild = v;
        }
    }
    for (int v : Adj[u])
    {
        if (v == p)
        {
            continue;
        }
        if (v != bigChild)
        {
            processDFS(v, u);
            for (int i = st[v]; i <= ed[v]; ++ i)
            {
                Del(order[i]);
            }
        }
    }
    if (bigChild != -1)
    {
        processDFS(bigChild, u);
    }
    Insert(u);
    for (int v : Adj[u])
    {
        if (v == p || v == bigChild)
        {
            continue;
        }
        for (int i = st[v]; i <= ed[v]; ++ i)
        {
            Insert(order[i]);
        }
    }
    for (pair<int, int> x : Query[u])
    {
        res[x.first] = Get(x.second);
    }
}
void solve()
{
    DFS(1, 0);
    processDFS(1, 0);
    for (int i = 1; i <= q; ++ i)
    {
        cout << res[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}