[Codeforces375D]Tree and Queries(莫隊算法) -开发者知识库

[Codeforces375D]Tree and Queries(莫隊算法) -开发者知识库,第1张

題意:給定一棵樹,每個節點有顏色,對於每個詢問(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;
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复