题意：
给一棵树，每个节点有一个颜色，询问x为根的子树，出现次数大于等于k的颜色个数。
输入格式：
第一行 2 个数 n,m 表示节点数和询问数。
接下来一行 n 个数，第 i 个数 ci 表示节点 i 的颜色。
接下来 n-1 行，每行两个数 a,b 表示一条边。
接下来 m 行，每行两个数 x,k 表示一组询问。
数据范围： $n.m,c,k in [1,10^5]$
显然可以 $dsu on tree$
可以用权值树状数组直接维护当前每个出现次数大于等于 $k$ 的颜色数量
但是因为每次修改都只有加 $1$ 或减 $1$
所以可以直接维护 $ans[i]$ 表示出现次数大于等于 $i$ 的颜色数量
具体代码就可以这样维护：
//cnt是每种颜色当前出现次数 inline void ins(int c) { cnt[c]++; ans[cnt[c]]++; } inline void del(int c) { ans[cnt[c]]--; cnt[c]--; }
其他就是 $dsu on tree$ 的基本操作了
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e6+7; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int &a,int &b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; } int n,m,col[N],Ans[N]; struct dat{ int x,k,id;//以节点x为根,出现次数大于等于k的询问,编号为id inline bool operator < (const dat &tmp) const { return x<tmp.x; } }d[N];//存询问并准备把询问按x排序 int sz[N],son[N]; void dfs1(int x,int fa) { sz[x]=1; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(v==fa) continue; dfs1(v,x); sz[x]+=sz[v]; if(sz[v]>sz[son[x]]) son[x]=v; } } int id[N],dfs_clock,cnt[N],ans[N];//id是dfs序为i的节点编号 inline void ins(int c) { cnt[c]++; ans[cnt[c]]++; } inline void del(int c) { ans[cnt[c]]--; cnt[c]--; } inline void work(int x)//处理与节点x有关的询问 { for(int i=lower_bound(d+1,d+m+1,(dat){x,0,0})-d ; d[i].x==x ; i++) Ans[d[i].id]=ans[d[i].k]; } void dfs2(int x,int fa,bool flag)//flag判断是否要清空子树 { id[++dfs_clock]=x; int L=dfs_clock;//L是轻儿子子树左区间 if(!son[x]) { ins(col[x]); work(x); if(!flag) del(col[x]); return; } //注意上面对于叶节点的特判中要先ins再work再del for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(v==fa||v==son[x]) continue; dfs2(v,x,0); } int R=dfs_clock;//轻儿子子树右区间 dfs2(son[x],x,1); for(int i=L;i<=R;i++) ins( col[id[i]] ); work(x); if(!flag) for(int i=L;i<=dfs_clock;i++) del( col[id[i]] );//注意清除的区间不是[L,R] } int main() { n=read(),m=read(); int a,b; for(int i=1;i<=n;i++) col[i]=read(); for(int i=1;i<n;i++) { a=read(),b=read(); add(a,b); add(b,a); } dfs1(1,0); for(int i=1;i<=m;i++) d[i].x=read(),d[i].k=read(),d[i].id=i; sort(d+1,d+m+1);//离散化 dfs2(1,0,1); for(int i=1;i<=m;i++) printf("%d ",Ans[i]); return 0; }