[Codeforces375D]Tree and Queries(莫队算法)

题意：给定一棵树，每个节点有颜色，对于每个询问（u，k)询问以u为根节点的子树下有多少种颜色出现次数>=k

因为是子树，跟dfs序有关，转化为一段区间，可以用莫队算法求解

直接用一个数组统计出现次数>=k的颜色

Code

#include <cstdio>

#include <algorithm>

#include <cmath>

#define N 100010

using namespace std;

int n,m,A[N],bl[N],Ans[N],dfn[N],sum[N],tot,head[N],sz[N],col[N],tw[N];

struct node{int to,nex;}e[N*2];

struct info{

	int l,r,k,id;

	friend bool operator <(info a,info b){

		return (bl[a.l]==bl[b.l])?a.r<b.r:a.l<b.l;

	}

}q[N];

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*10+ch-'0';ch=getchar();}

    return x*f;

}

void upd(int x,int d){

	if(d>0) sum[++col[tw[x]]]++;

	else sum[col[tw[x]]--]--;

}

void Link(int u,int v){

	e[++tot].nex=head[u];e[tot].to=v;head[u]=tot;

}

void dfs(int u,int fa){

	dfn[u]=++tot,sz[u]=1,tw[tot]=A[u];

	for(int i=head[u];i;i=e[i].nex)

		if(e[i].to!=fa) dfs(e[i].to,u),sz[u]+=sz[e[i].to];

}

int main(){

	n=read(),m=read();int blo=sqrt(n);

	for(int i=1;i<=n;++i) A[i]=read(),bl[i]=i/blo+1;

	for(int i=1;i<n;++i){

		int u=read(),v=read();

		Link(u,v),Link(v,u);

	}

	tot=0,dfs(1,0);

	for(int i=1;i<=m;++i){

		int u=read(),k=read();

		q[i]=(info){dfn[u],dfn[u]+sz[u]-1,k,i};

	}

	sort(q+1,q+m+1);

	for(int i=1,l=1,r=0;i<=m;++i){

		for(;l<q[i].l;l++) upd(l,-1);

		for(;l>q[i].l;l--) upd(l-1,1);

		for(;r<q[i].r;r++) upd(r+1,1);

		for(;r>q[i].r;r--) upd(r,-1);

		Ans[q[i].id]=sum[q[i].k];

	}

	for(int i=1;i<=m;printf("%d\n",Ans[i++]));

	return 0;

}