首先注意题意，是统计>=k的个数。
那么首先考虑一下暴力的思路，用cnt[i]来表示次数>=i的个数。
考虑删去一个点，那么cnt[c[i]]--。注意的是cnt[c[i]-1]不需要++，一开始误区就在这了，因为cnt[c[i]-1]还是满足>=c[i]-1的。
那么加入一个点，cnt[c[i]+1]++。
因为这里是树上的询问，但是我们可以对询问进行序列化，因为都是询问某个点的子树，显然可以dfs序来做。
区间L,r显然是连续的dfs序。那么，我们就可以离线询问，然后莫队分块即可。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5+5; const int M = 12005; const LL Mod = 199999; #define rg register #define pi acos(-1) #define INF 1e5+1 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int c[N],dfn[N],ssize[N],rk[N],vis[N],tim = 0,cnt[N],ans[N];//cnt[i]表示次数>=i的个数 vector<int> G[N]; struct Node{int L,r,id,bl,k;}p[N]; bool cmp(Node a,Node b) { if(a.bl != b.bl) return a.L < b.L; if(a.bl&1) return a.r < b.r; return a.r > b.r; } void dfs(int u,int fa) { dfn[u] = ++tim; rk[tim] = u; ssize[u] = 1; for(auto v : G[u]) { if(v == fa) continue; dfs(v,u); ssize[u] += ssize[v]; } } void del(int x) { x = rk[x]; int col = c[x]; cnt[vis[col]]--; vis[col]--; } void add(int x) { x = rk[x]; int col = c[x]; vis[col]++; cnt[vis[col]]++; } int main() { int n,m;n = read(),m = read(); for(rg int i = 1;i <= n;++i) c[i] = read(); for(rg int i = 1;i < n;++i) { int x,y;x = read(),y = read(); G[x].push_back(y);G[y].push_back(x); } dfs(1,0); int blsize = sqrt(n); for(rg int i = 1;i <= m;++i) { int u,k;u = read(),k = read(); p[i].L = dfn[u],p[i].r = dfn[u]+ssize[u]-1,p[i].k = k; p[i].id = i,p[i].bl = (p[i].L-1)/blsize+1; } sort(p+1,p+m+1,cmp); int L = 1,r = 0; for(rg int i = 1;i <= m;++i) { while(L < p[i].L) del(L++); while(L > p[i].L) add(--L); while(r > p[i].r) del(r--); while(r < p[i].r) add(++r); ans[p[i].id] = cnt[p[i].k]; } for(rg int i = 1;i <= m;++i) printf("%d ",ans[i]); system("pause"); }