[cf375D]Tree and Queries

Description

给定一棵树，每个节点有颜色。t个询问，求以v为根的子树中有多少种颜色满足该颜色的节点个数>k。

Solution

dfs序+莫队。

#include
using namespace std;

const int N=100005;
struct graph{
	int nxt,to;
}e[N<<1];
struct query{
	int l,r,k,n;
}q[N];
int fro[N],beh[N],num[N];//dfs序 
int f[N],s[N],tmp[N];//莫队 tmp[i]：s[x]>=i的x的个数
int g[N],c[N],ans[N],n,m,t,cnt;
void adde(int x,int y){
	e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
void dfs(int u){
	fro[u]=++cnt;num[cnt]=u;
	for(int i=g[u];i;i=e[i].nxt)
		if(!fro[e[i].to]){
			dfs(e[i].to);
		}
	beh[u]=cnt;
}
bool cmp(query a,query b){
	if(f[a.l]!=f[b.l]) return f[a.l]q[i].r){
			remove(r);--r;
		}
		while(l>q[i].l){
			--l;add(l);
		}
		while(l