题目
思路
唯有水题暖人心
只用子树的树，当然dfs序列 区间查询出现k次的数字的个数 nub[i]记录出现次数大于i的数字个数 发现只是O(1)的转移，想想就OK了代码
ps:为了更好地阅读，我加一段cpp吧
void add(int x){ hav[x]++; nub[hav[x]]++;}void delet(int x){ nub[hav[x]]--; hav[x]--;}FOR(i,1,m){ while(l > Q[i].s) add(a[b[--l]]); while(l < Q[i].s) delet(a[b[l++]]); while(r < Q[i].t) add(a[b[++r]]); while(r > Q[i].t) delet(a[b[r--]]); Q[i].ans=nub[Q[i].k];} #include#define FOR(i,a,b) for(int i=a;i<=b;++i)using namespace std;const int maxn=1e5+7;int n,m,a[maxn],b[maxn],begg[maxn],endd[maxn],js,nub[maxn],hav[maxn];;int head[maxn<<1],tot,belong[maxn];struct node{ int s,t,k,id,ans;}Q[maxn];bool cmp1(const node &a,const node &b){ return belong[a.s]==belong[b.s] ? a.t '9';s=getchar()) if(s=='-') f=-1; for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0'; return x*f;}void dfs(int u,int f){ b[++js]=u; begg[u]=js; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(v==f) continue; dfs(v,u); } endd[u]=js;}int main(){ n=read(),m=read(); int k=sqrt(n); FOR(i,1,n) a[i]=read(); FOR(i,1,n) belong[i]=(i-1)/k+1; FOR(i,1,n-1) { int x=read(),y=read(); add_edge(x,y); add_edge(y,x); } dfs(1,0); FOR(i,1,m) { int x=read(),y=read(); Q[i].s=begg[x]; Q[i].t=endd[x]; Q[i].k=y; Q[i].id=i; } sort(Q+1,Q+1+m,cmp1); int l=1,r=0; FOR(i,1,m) { while(l > Q[i].s) hav[a[b[--l]]]++,nub[hav[a[b[l]]]]++; while(l < Q[i].s) nub[hav[a[b[l]]]]--,hav[a[b[l++]]]--; while(r < Q[i].t) hav[a[b[++r]]]++,nub[hav[a[b[r]]]]++; while(r > Q[i].t) nub[hav[a[b[r]]]]--,hav[a[b[r--]]]--; Q[i].ans=nub[Q[i].k]; } sort(Q+1,Q+1+m,cmp2); FOR(i,1,m) printf("%d\n",Q[i].ans);}
