感觉CF的题目名都好朴素的样子
首先这题显然是个dsu on tree 但是我不会。
其次这题显然是个莫队。这我会啊！
然后会发现好像不是很对劲。因为每次询问都有一个k，貌似和传统的莫队数颜色有点不一样。
本蒟蒻看到这里的时候内心是崩溃的。然后就看了一眼题解。
然后我就迷惑了。震惊，前缀和还可以O(1)修改，活到爆！
然后经过郭神的一番论证以后，我惊讶的发现，这个题还真能O(1)修改前缀和。
首先，两个数组。sum[i]表示出现次数大于i的颜色的数量。val[i]表示颜色i的出现次数。
那么考虑莫队做法，当上一个询问的答案转移到当下的答案时，我们假设颜色i的数量要++。那么sum[val[i]+1]++;
但是会发现，出现次数是(val[i]+1)的颜色数量+1，而对应的，出现次数是(val[i])的颜色数量就要-1。也就是说，每次对颜色的修改，只会涉及到sum数组的单点，而不会涉及到前缀（或后缀）。
弄清楚这个，代码就很简单了。做个dfn序，跑普通莫队即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({ register int x = 0, f = 1; register char c = gc(); while(c < '0' || c > '9') { if (c == '-') f = -1; c = gc();} while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc(); f * x; })
char buf[1 << 20], *p1, *p2;
struct node{
int to,next;
}edge[maxn<<1];
int n,cnt,Time,m,ss;
int size[maxn],head[maxn],dfn[maxn],a[maxn],w[maxn],belong[maxn],sum[maxn],res[maxn],val[maxn];
struct Q{
int l,r,data,k;
}b[maxn];
void add(int from,int to){
edge[++cnt].to=to;
edge[cnt].next=head[from];
head[from]=cnt;
}
void dfs1(int u,int f){
size[u]=1;
dfn[u]=++Time;
w[Time]=a[u];
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(v==f) continue;
dfs1(v,u);
size[u]+=size[v];
}
}
bool cmp(Q x,Q y){
return belong[x.l]!=belong[y.l] ? x.l<y.l : belong[x.l]&1 ? x.r<y.r : x.r>y.r ;
}
void Solve(){
n=read(); m=read();
ss=sqrt(n);
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) belong[i]=(i-1)/ss+1;
for(int i=1,x,y;i<n;++i) {
x=read();
y=read();
add(x,y);
add(y,x);
}
dfs1(1,0);
for(int i=1,x;i<=m;++i){
x=read();
b[i].k=read();
b[i].data=i;
b[i].l=dfn[x];
b[i].r=dfn[x]+size[x]-1;
}
sort(b+1,b+m+1,cmp);
int l=1,r=0,ans=0;
for(int i=1;i<=m;++i){
while(l>b[i].l){
--l;
val[w[l]]++;
sum[val[w[l]]]++;
}
while(r<b[i].r){
++r;
val[w[r]]++;
sum[val[w[r]]]++;
}
while(l<b[i].l){
sum[val[w[l]]]--;
val[w[l]]--;
l++;
}
while(r>b[i].r){
sum[val[w[r]]]--;
val[w[r]]--;
r--;
}
res[b[i].data]=sum[b[i].k];
}
for(int i=1;i<=m;++i) printf("%d
",res[i]);
}
int main(){
Solve();
return 0;
}